LeetCode 830. Positions of Large Groups



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".

Example 4:

Input: s = "aba"
Output: []


  • 1 <= s.length <= 1000
  • s contains lower-case English letters only.


Iterate the list with two pointers. If the fast pointer is different than the slow pointer letter, move the slow to the fast position, and reset the counter.

Python Solution

class Solution:
    def largeGroupPositions(self, s: str) -> List[List[int]]:
        results = []
        i = 0
        j = 0
        visited = set()
        while j < len(s):
            if len(visited) == 0:
                j += 1
            elif s[j] not in visited:                
                if j - i > 2:
                    results.append([i, j - 1])
                visited = set()
                i = j
                j += 1
        if len(visited) > 0 and j - i > 2:
            results.append([i, j - 1])
        return results
  • Time Complexity: O(Nlog(N)).
  • Space Complexity: O(N).

Leave a Reply

Your email address will not be published. Required fields are marked *