Scale Engineer

Positions of Large Groups

Easy
#0784Time: 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: 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).
Data structures
String

Prompt

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:

"xxxx" is the only

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

2 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

Time

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

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).

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem