Skip to content

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.

Solutions

Solution 1: Two Pointers

We use two pointers \(i\) and \(j\) to find the start and end positions of each group, then check if the group length is greater than or equal to \(3\). If so, we add it to the result array.

The time complexity is \(O(n)\), where \(n\) is the length of the string \(s\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def largeGroupPositions(self, s: str) -> List[List[int]]:
        i, n = 0, len(s)
        ans = []
        while i < n:
            j = i
            while j < n and s[j] == s[i]:
                j += 1
            if j - i >= 3:
                ans.append([i, j - 1])
            i = j
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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(List.of(i, j - 1));
            }
            i = j;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<vector<int>> largeGroupPositions(string s) {
        int n = s.size();
        int i = 0;
        vector<vector<int>> ans;
        while (i < n) {
            int j = i;
            while (j < n && s[j] == s[i]) {
                ++j;
            }
            if (j - i >= 3) {
                ans.push_back({i, j - 1});
            }
            i = j;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
func largeGroupPositions(s string) [][]int {
    i, n := 0, len(s)
    ans := [][]int{}
    for i < n {
        j := i
        for j < n && s[j] == s[i] {
            j++
        }
        if j-i >= 3 {
            ans = append(ans, []int{i, j - 1})
        }
        i = j
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
function largeGroupPositions(s: string): number[][] {
    const n = s.length;
    const ans: number[][] = [];

    for (let i = 0; i < n; ) {
        let j = i;
        while (j < n && s[j] === s[i]) {
            ++j;
        }
        if (j - i >= 3) {
            ans.push([i, j - 1]);
        }
        i = j;
    }

    return ans;
}

Comments