Positions of Large Groups

EASY

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.

Approaches

Checkout 2 different approaches to solve Positions of Large Groups. Click on different approaches to view the approach and algorithm in detail.

Two-Pass Approach

This method involves two separate iterations over the data. The first pass identifies all consecutive groups of identical characters and stores their start and end indices. The second pass then filters this list to find only the "large" groups (those with a length of 3 or more).

Algorithm

1. Initialize an empty list, allGroups, to store the intervals of every group.
1. Iterate through the input string s using a pointer i to find the start and end of each group of identical characters.
1. For each group found, starting at index start and ending at end, add the interval [start, end] to the allGroups list.
1. After the first pass is complete, initialize another empty list, result.
1. Iterate through the allGroups list. For each interval [start, end], calculate its length (end - start + 1).
1. If the length is 3 or greater, add the interval to the result list.
1. Finally, return the result list.

This approach separates the problem into two distinct steps. First, we iterate through the string to identify every single group of consecutive characters, regardless of size. We store the start and end indices of each of these groups in an intermediate list. Once we have a complete list of all groups, we perform a second pass over this new list. In this second pass, we check the size of each group and add only the ones that meet the 'large' criteria (length >= 3) to our final result list.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<List<Integer>> largeGroupPositions(String s) {
        List<List<Integer>> allGroups = new ArrayList<>();
        int n = s.length();
        if (n == 0) {
            return new ArrayList<>();
        }
        
        int i = 0;
        while (i < n) {
            int start = i;
            i++;
            while (i < n && s.charAt(i) == s.charAt(start)) {
                i++;
            }
            allGroups.add(Arrays.asList(start, i - 1));
        }

        List<List<Integer>> result = new ArrayList<>();
        for (List<Integer> group : allGroups) {
            int start = group.get(0);
            int end = group.get(1);
            if (end - start + 1 >= 3) {
                result.add(group);
            }
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(N), where N is the length of the string. The first pass to find all groups takes O(N) time as we traverse the string once. The second pass to filter for large groups takes O(M) time, where M is the number of groups. Since M is at most N, the total time complexity is O(N) + O(M) = O(N).Space Complexity: O(M), where M is the total number of groups. We need extra space to store the intervals of all groups. In the worst case (e.g., a string with all unique characters like "abcdef"), M can be equal to N, the length of the string. Thus, the space complexity is O(N).

Pros and Cons

Pros:

Conceptually simple, as it separates the logic of finding groups from filtering them.

Cons:

Requires extra space to store all groups, which is less memory-efficient than a single-pass solution.
Involves two separate loops over the data, which can be slightly slower in practice than a single loop.

Code Solutions

Checking out 3 solutions in different languages for Positions of Large Groups. Click on different languages to view the code.

class Solution {
public
  List<List<Integer>> largeGroupPositions(String s) {
    int n = s.length();
    int i = 0;
    List<List<Integer>> ans = new ArrayList<>();
    while (i < n) {
      int j = i;
      while (j < n && s.charAt(j) == s.charAt(i)) {
        ++j;
      }
      if (j - i >= 3) {
        ans.add(Arrays.asList(i, j - 1));
      }
      i = j;
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Positions of Large Groups

Data Structures:

String