# Positions of Large Groups
**Difficulty:** EASY
[External](https://leetcode.com/problems/positions-of-large-groups)
Canonical: https://scaleengineer.com/dsa/problems/positions-of-large-groups
**Data structures:** String
---
## 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 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.

# Approaches
## Two-Pass Approach
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).
**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).
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- 1. Initialize an empty list, `allGroups`, to store the intervals of every group.
- 2. Iterate through the input string `s` using a pointer `i` to find the start and end of each group of identical characters.
- 3. For each group found, starting at index `start` and ending at `end`, add the interval `[start, end]` to the `allGroups` list.
- 4. After the first pass is complete, initialize another empty list, `result`.
- 5. Iterate through the `allGroups` list. For each interval `[start, end]`, calculate its length (`end - start + 1`).
- 6. If the length is 3 or greater, add the interval to the `result` list.
- 7. Finally, return the `result` list.

## Single-Pass (Two-Pointer) Approach
This is the most efficient approach. It uses a single pass through the string to identify large groups. Two pointers are used: one to mark the start of a potential group (`i`) and another to find its end (`j`). The check for a large group is performed as soon as a group is identified, avoiding the need for intermediate storage.
**Time:** O(N), where N is the length of the string. Each character is visited a constant number of times by the pointers `i` and `j`, as they only move forward through the string. This results in a linear time complexity. · **Space:** O(1) if we exclude the space required for the output list. If the output list is considered, the space complexity is O(K), where K is the number of large groups. This is more memory-efficient than the two-pass approach, which requires O(M) space for all groups (where M >= K).
**Pros:** Optimal time complexity, as it requires only a single pass over the string.; Optimal space complexity, as it doesn't use any intermediate data structures to store all groups.
**Cons:** The logic for updating the pointers might be slightly more complex to grasp initially compared to a two-pass approach.
### Explanation
This optimal solution iterates through the string just once. It maintains a pointer `i` that marks the beginning of the current group of identical characters. A second pointer, `j`, scans forward from `i` to find the end of this group. When the character at `j` differs from the character at `i`, or `j` reaches the end of the string, the group is identified. We then calculate the group's length. If the length is 3 or more, we add its start and end indices (`i` and `j-1`) to our result list. The main pointer `i` is then updated to `j`'s position to start searching for the next group. This process continues until the entire string has been scanned.

```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<List<Integer>> largeGroupPositions(String s) {
        List<List<Integer>> result = new ArrayList<>();
        int n = s.length();
        int i = 0; // start of the group
        while (i < n) {
            int j = i;
            while (j < n && s.charAt(j) == s.charAt(i)) {
                j++;
            }
            // The group of characters s.charAt(i) is from index i to j-1
            if (j - i >= 3) {
                result.add(Arrays.asList(i, j - 1));
            }
            // Move to the start of the next potential group
            i = j;
        }
        return result;
    }
}
```
### Algorithm
- 1. Initialize an empty list `result` to store the final intervals.
- 2. Use a pointer `i` to iterate through the string from the beginning to the end. This pointer will mark the start of each new group.
- 3. Use a second pointer `j` to find the end of the current group. Starting from `i`, advance `j` as long as it's within the string bounds and the character at `j` is the same as the character at `i`.
- 4. Once the character changes or the end of the string is reached, the group spans from index `i` to `j-1`.
- 5. Calculate the length of this group: `length = j - i`.
- 6. If `length >= 3`, it's a large group. Add the interval `[i, j-1]` to the `result` list.
- 7. Move the `i` pointer to `j` to begin searching for the next group from where the last one ended.
- 8. Repeat the process until `i` has traversed the entire string.

# Solutions
### Java

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

```

### CPP

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

```

### Python

```python
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

```