# LeetCode 830: Positions of Large Groups

## Problem Restatement

We are given a string `s` containing lowercase English letters.

Consecutive equal characters form a group.

For example:

```python
s = "abbxxxxzyy"
```

The groups are:

| Group | Interval |
|---|---|
| `"a"` | `[0, 0]` |
| `"bb"` | `[1, 2]` |
| `"xxxx"` | `[3, 6]` |
| `"z"` | `[7, 7]` |
| `"yy"` | `[8, 9]` |

A group is large if its length is at least `3`.

We need to return the start and end indices of every large group, sorted by increasing start index. Since we scan from left to right, the result naturally has this order.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A string `s` |
| Output | A list of intervals `[start, end]` |
| Large group | A consecutive group with length at least `3` |
| Indexing | `start` and `end` are inclusive |

Function shape:

```python
class Solution:
    def largeGroupPositions(self, s: str) -> list[list[int]]:
        ...
```

## Examples

Example 1:

```python
s = "abbxxxxzzy"
```

The groups are:

```python
"a", "bb", "xxxx", "zz", "y"
```

Only `"xxxx"` has length at least `3`.

It starts at index `3` and ends at index `6`.

So the answer is:

```python
[[3, 6]]
```

Example 2:

```python
s = "abc"
```

The groups are:

```python
"a", "b", "c"
```

No group has length at least `3`.

So the answer is:

```python
[]
```

Example 3:

```python
s = "abcdddeeeeaabbbcd"
```

The large groups are:

| Group | Interval |
|---|---|
| `"ddd"` | `[3, 5]` |
| `"eeee"` | `[6, 9]` |
| `"bbb"` | `[12, 14]` |

So the answer is:

```python
[[3, 5], [6, 9], [12, 14]]
```

## First Thought: Count Each Group

The problem is asking us to identify runs of equal adjacent characters.

A run starts at some index `i`.

It continues while the next characters are the same as `s[i]`.

Once the character changes, the run ends.

If the run length is at least `3`, we add its interval to the answer.

## Key Insight

We do not need any extra data structure to group the string.

Use two pointers:

| Pointer | Meaning |
|---|---|
| `i` | Start index of the current group |
| `j` | First index after the current group |

For each group:

1. Set `j = i`.
2. Move `j` while `s[j] == s[i]`.
3. The group is from `i` to `j - 1`.
4. Its length is `j - i`.
5. If `j - i >= 3`, add `[i, j - 1]`.
6. Move `i` to `j`.

## Algorithm

Initialize an empty answer list.

Start at index `i = 0`.

While `i` is inside the string:

1. Let `j = i`.
2. Move `j` forward while `j < len(s)` and `s[j] == s[i]`.
3. Check the group length.
4. If the length is at least `3`, append `[i, j - 1]`.
5. Set `i = j` to move to the next group.

## Walkthrough

Use:

```python
s = "abbxxxxzzy"
```

Start with `i = 0`.

The current character is `"a"`.

The group is:

```python
"a"
```

Its interval is `[0, 0]`, and its length is `1`.

Not large.

Move to `i = 1`.

The current character is `"b"`.

The group is:

```python
"bb"
```

Its interval is `[1, 2]`, and its length is `2`.

Not large.

Move to `i = 3`.

The current character is `"x"`.

The group is:

```python
"xxxx"
```

Its interval is `[3, 6]`, and its length is `4`.

This is large, so we add:

```python
[3, 6]
```

Move to `i = 7`.

The current character is `"z"`.

The group is:

```python
"zz"
```

Its interval is `[7, 8]`, and its length is `2`.

Not large.

Move to `i = 9`.

The current character is `"y"`.

The group is:

```python
"y"
```

Its interval is `[9, 9]`, and its length is `1`.

Not large.

Final answer:

```python
[[3, 6]]
```

## Correctness

The algorithm processes the string from left to right.

At the start of each iteration, `i` is the first index of a group that has not been processed yet.

The inner loop advances `j` until either the string ends or `s[j]` differs from `s[i]`. Therefore, all indices from `i` to `j - 1` belong to the same group, and index `j`, if it exists, starts a different group.

So `[i, j - 1]` is exactly the interval of the current group.

The algorithm adds this interval exactly when:

```python
j - i >= 3
```

which is exactly the definition of a large group.

After processing the group, the algorithm sets:

```python
i = j
```

so the next iteration starts at the next unprocessed group.

Thus every group is checked once, every large group is included, and no non-large group is included.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each character is visited once by the scan |
| Space | `O(1)` extra | Apart from the output list, only pointers are used |

The output list can contain up to `O(n)` intervals in the worst case, but auxiliary memory is constant.

## Implementation

```python
class Solution:
    def largeGroupPositions(self, s: str) -> list[list[int]]:
        answer = []
        n = len(s)
        i = 0

        while i < n:
            j = i

            while j < n and s[j] == s[i]:
                j += 1

            if j - i >= 3:
                answer.append([i, j - 1])

            i = j

        return answer
```

## Code Explanation

We store the result here:

```python
answer = []
```

The pointer `i` marks the start of the current group:

```python
i = 0
```

For each group, we start `j` at the same position:

```python
j = i
```

Then we extend `j` while the characters stay equal:

```python
while j < n and s[j] == s[i]:
    j += 1
```

When this loop ends, the group is:

```python
[i, j - 1]
```

Its length is:

```python
j - i
```

If that length is at least `3`, we save the interval:

```python
if j - i >= 3:
    answer.append([i, j - 1])
```

Finally, we skip the whole group:

```python
i = j
```

and continue with the next group.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.largeGroupPositions("abbxxxxzzy") == [[3, 6]]
    assert s.largeGroupPositions("abc") == []
    assert s.largeGroupPositions("abcdddeeeeaabbbcd") == [[3, 5], [6, 9], [12, 14]]
    assert s.largeGroupPositions("aaa") == [[0, 2]]
    assert s.largeGroupPositions("aaaa") == [[0, 3]]
    assert s.largeGroupPositions("aaabbb") == [[0, 2], [3, 5]]
    assert s.largeGroupPositions("a") == []

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `"abbxxxxzzy"` | Standard case with one large group |
| `"abc"` | No large groups |
| `"abcdddeeeeaabbbcd"` | Multiple large groups |
| `"aaa"` | Minimum large group length |
| `"aaaa"` | Group longer than minimum |
| `"aaabbb"` | Adjacent large groups |
| `"a"` | Minimum string length |