Problem

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 everylarge group sorted in increasing order by start index.

Examples

Example 1

1
2
3

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

Example 2

1
2
3

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

Example 3

1
2
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

Intuition

We scan the string and track the start and end of each group. If the group length is at least 3, we record its interval.

Approach

  1. Initialize start = 0. For each character, if it differs from the previous, check if the group length is >= 3 and record it.
  2. At the end, check the last group.
  3. Return the list of intervals.

Code

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

#include <vector>
#include <string>
using namespace std;
vector<vector<int>> largeGroupPositions(string s) {
    vector<vector<int>> res;
    int n = s.size(), start = 0;
    for (int i = 1; i <= n; ++i) {
        if (i == n || s[i] != s[start]) {
            if (i - start >= 3) res.push_back({start, i-1});
            start = i;
        }
    }
    return res;
}
Go
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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

import java.util.*;
class Solution {
    public List<List<Integer>> largeGroupPositions(String s) {
        List<List<Integer>> res = new ArrayList<>();
        int n = s.length(), start = 0;
        for (int i = 1; i <= n; ++i) {
            if (i == n || s.charAt(i) != s.charAt(start)) {
                if (i - start >= 3) res.add(Arrays.asList(start, i-1));
                start = i;
            }
        }
        return res;
    }
}
Kotlin
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

fun largeGroupPositions(s: String): List<List<Int>> {
    val res = mutableListOf<List<Int>>()
    var start = 0
    for (i in 1..s.length) {
        if (i == s.length || s[i] != s[start]) {
            if (i - start >= 3) res.add(listOf(start, i-1))
            start = i
        }
    }
    return res
}
Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def largeGroupPositions(s: str) -> list[list[int]]:
    res = []
    n = len(s)
    start = 0
    for i in range(1, n+1):
        if i == n or s[i] != s[start]:
            if i - start >= 3:
                res.append([start, i-1])
            start = i
    return res
Rust
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

fn large_group_positions(s: String) -> Vec<Vec<i32>> {
    let s = s.as_bytes();
    let n = s.len();
    let mut res = vec![];
    let mut start = 0;
    for i in 1..=n {
        if i == n || s[i] != s[start] {
            if i - start >= 3 {
                res.push(vec![start as i32, (i-1) as i32]);
            }
            start = i;
        }
    }
    res
}
TypeScript
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

export function largeGroupPositions(s: string): number[][] {
    const res: number[][] = [];
    let start = 0;
    for (let i = 1; i <= s.length; ++i) {
        if (i === s.length || s[i] !== s[start]) {
            if (i - start >= 3) res.push([start, i-1]);
            start = i;
        }
    }
    return res;
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1) (ignoring output).