Leetcode problem: 830. Positions of Large Groups

Description:

In a string s of lowercase letters, these letters form consecutive groups of the same character.

For example, a string like s = "abbxxxxzyy" has the groups "a", "bb", "xxxx", "z", and "yy".

A group is identified by an interval [start, end], where start and end denote the start and end indices (inclusive) of the group. In the above example, "xxxx" has the interval [3,6].

A group is considered large if it has 3 or more characters.

Return the intervals of every large group sorted in increasing order by start index.

Example 1:

Input: s = "abbxxxxzzy"
Output: [[3,6]]
Explanation: "xxxx" is the only large group with start index 3 and end index 6.

Example 2:

Input: s = "abc"
Output: []
Explanation: We have groups "a", "b", and "c", none of which are large groups.

Example 3:

Input: s = "abcdddeeeeaabbbcd"
Output: [[3,5],[6,9],[12,14]]
Explanation: The large groups are "ddd", "eeee", and "bbb".

Constraints:

• 1 <= s.length <= 1000
• s contains lowercase English letters only.

Solution:

class Solution {
    public List<List<Integer>> largeGroupPositions(String s) {
        int len = s.length();
        List<List<Integer>> list = new ArrayList<>();
        int startIndex = 0;
        int endIndex = 0;
        int count = 0;
        boolean isMatch = true;

        for (int i = 1; i < len; i++) {
            if (s.charAt(i) == s.charAt(i - 1)) {
                count++;
                if (isMatch) {
                    isMatch = false;
                    startIndex = i - 1;
                }
            } else {
                endIndex = i - 1;
                isMatch = true;
                if (count >= 2) {
                    List<Integer> listMatch = new ArrayList<>();
                    listMatch.add(startIndex);
                    listMatch.add(endIndex);
                    list.add(listMatch);
                }
                count = 0;
            }
        }

        if (count >= 2) {
            endIndex = len - 1;
            List<Integer> listMatch = new ArrayList<>();
            listMatch.add(startIndex);
            listMatch.add(endIndex);
            list.add(listMatch);
        }
        return list;
    }
}

Explanation:

Step 1: Initialize variables

int len = s.length();
List<List<Integer>> list = new ArrayList<>();
int startIndex = 0;
int endIndex = 0;
int count = 0;
boolean isMatch = true;

• len → length of the string.
• list → the result list of lists storing [start, end] of large groups.
• startIndex → marks the start of a potential group.
• endIndex → marks the end of a group.
• count → counts how many consecutive identical characters have been found.
• isMatch → flag to indicate whether a new group has started.

Step 2: Iterate through the string

for (int i = 1; i < len; i++) {
    if (s.charAt(i) == s.charAt(i - 1)) {
        count++;
        if (isMatch) {
            isMatch = false;
            startIndex = i - 1;
        }
    } else {
        endIndex = i - 1;
        isMatch = true;
        if (count >= 2) {
            List<Integer> listMatch = new ArrayList<>();
            listMatch.add(startIndex);
            listMatch.add(endIndex);
            list.add(listMatch);
        }
        count = 0;
    }
}

• Loop starts at i = 1 because we compare each character with the previous one.
• If s.charAt(i) == s.charAt(i-1):
  • We are in a sequence of identical characters.
  • Increment count.
  • If isMatch is true (start of a new group), set startIndex to i-1 and mark isMatch as false.
• Else (current char differs from previous):
  • endIndex = i-1 → end of the previous group.
  • Reset isMatch = true → ready for the next group.
  • If count >= 2 → there were at least 3 characters in the group (because count counts repeated chars after the first one).
    • Add [startIndex, endIndex] to list.
  • Reset count = 0.

Step 3: Handle the last group

if (count >= 2) {
    endIndex = len - 1;
    List<Integer> listMatch = new ArrayList<>();
    listMatch.add(startIndex);
    listMatch.add(endIndex);
    list.add(listMatch);
}

• After the loop, we might have a group that goes until the last character.
• If count >= 2, add it to the list.

Step 4: Return the result

return list;

• The list now contains all [start, end] pairs of large groups.

Example Run

Input: "abbxxxxzyy"

Output: [[3,6]]

✅ Summary

• The code detects sequences of 3 or more repeated characters.
• It tracks start and end indices for each sequence.
• Handles groups at the end of the string properly.
• Uses count and isMatch to manage group detection.