Positions of Large Groups

Problem Statement

In a given string s composed entirely of lowercase English letters, certain characters cluster together to form what are called "groups." These groups are sequences where the same character appears consecutively without interruption by a different character. The concept can be visualized by segmenting the string into these sequences. Each group can be represented by the indices marking its start and end within the string.

For instance, consider the string s = "abbxxxxzyy"; this splits into the groups ["a", "bb", "xxxx", "z", "yy"]. Here, the group "xxxx" is represented by the interval [3, 6], indicating that 'x' spans from index 3 to index 6 in the string.

Only the groups which are formed by three or more consecutive characters are deemed "large." The task is to identify all such large groups and return their starting and ending indices in an array formatted as intervals, with these intervals sorted by their starting index.

Examples

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.

Approach and Intuition

Given the problem and example scenarios, our approach can be outlined as follows:

1. Begin by initializing the required markers or points in our iteration: start to note the beginning of a group, end for the conclusion of the current analyzed group, and an empty list result to store the intervals of large groups identified.

2. Iterate through the string using an index that helps track characters. Compare each character with the next one:

   • If they are the same, move to the next character.
   • If they differ, the end of a group is identified:
     • Calculate the group's length.
     • If this length is three or more (making it a 'large' group):
       • Capture the start and end indices of this large group in the result list.
     • Reset start to the current index to begin assessing the potential new group.

3. Post loop, ensure any remaining characters forming a large group are accounted for since the last group won't be followed by a change that triggers group storage inside the loop.

This procedure cyclically assesses each sequence for its eligibility as a 'large' group and then shifts to the next potential group in a straight-forward, linear pass through the string, ensuring all conditions and constraints are adhered to, and performance is maintained without unnecessary complexity. In each iteration, a decision is made whether to reset the start of a new group or to conclude and store the current group if it meets the criteria of being 'large'.

Solutions

class Solution {
    public List<List<Integer>> findLargeGroups(String str) {
        List<List<Integer>> result = new ArrayList<>();
        int start = 0, length = str.length(); // start is the start of each group
        for (int end = 0; end < length; ++end) {
            if (end == length-1 || str.charAt(end) != str.charAt(end+1)) {
                // [start, end] defines a group
                if (end-start+1 >= 3)
                    result.add(Arrays.asList(new Integer[]{start, end}));
                start = end + 1;
            }
        }
    
        return result;
    }
}