Positions of Large Groups

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

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.

Solution

Method 1 - Run-length Scan (Group Boundaries)

Intuition

We scan the string and track the group boundaries using start and end indices. If a group's length (end - start + 1) is at least 3, we record its interval in res.

Approach

1. Initialize start = 0 and n = len(s).
2. Iterate i from 1 to n (inclusive). When i == n or s[i] != s[start], the current group ends at i-1.
3. If the group length i - start is >= 3, append [start, i-1] to res.
4. Set start = i to begin the next group.
5. Return res.

Complexity

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

Code

C++

#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

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

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

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

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

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

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;
}