Positions of Large Groups

Difficulty: Easy | Acceptance: 54.00% | Paid: No Topics: String

In a string s of lowercase letters, these letters form consecutive groups of the same character.

For example, a string s = “abbxxxxzyy” has the groups “a”, “bb”, “xxxx”, “z”, and “yy”.

A group is considered large if it has 3 or more characters. We would like the starting and ending positions of every large group.

The final answer should be in lexicographic order.

Examples

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

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

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.

• Examples
• Constraints
• Approach 1: One Pass Iteration
• Approach 2: Two Pointers
• Approach 3: Regular Expressions

Examples

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

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

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.

Approach 1: One Pass Iteration

Intuition We iterate through the string once, keeping track of the start index of the current character group. When the character changes or we reach the end of the string, we check if the group length is 3 or more.

Steps

• Initialize an empty list res to store results and start = 0 to mark the beginning of the current group.
• Iterate through the string with index i from 0 to n (inclusive).
• If i reaches the end n or the current character s[i] differs from s[start], the current group has ended.
• Calculate the length of the group as i - start. If it is >= 3, add [start, i - 1] to res.
• Update start = i to begin a new group.

class Solution:
    def largeGroupPositions(self, s: str) -> list[list[int]]:
        res = []
        n = len(s)
        start = 0
        for i in range(n + 1):
            if i == n or s[i] != s[start]:
                if i - start >= 3:
                    res.append([start, i - 1])
                start = i
        return res

Complexity

• Time: O(n) where n is the length of the string. We traverse the string once.
• Space: O(1) auxiliary space, excluding the space required for the output list.
• Notes: This is the most efficient approach for this problem.

Approach 2: Two Pointers

Intuition We use two pointers, start and end, to define the boundaries of the current group. We expand the end pointer as long as the characters are the same.

Steps

• Initialize res and set i = 0.
• While i < n:
  • Set j = i.
  • While j < n and s[j] == s[i], increment j.
  • Now the group is from i to j - 1. If j - i >= 3, add [i, j - 1] to res.
  • Move i to j to start checking the next group.

class Solution:
    def largeGroupPositions(self, s: str) -> list[list[int]]:
        res = []
        n = len(s)
        i = 0
        while i < n:
            j = i
            while j < n and s[j] == s[i]:
                j += 1
            if j - i >= 3:
                res.append([i, j - 1])
            i = j
        return res

Complexity

• Time: O(n) as each character is visited at most twice (once by i and once by j).
• Space: O(1) auxiliary space.
• Notes: This approach is logically equivalent to the one-pass iteration but explicitly uses two pointers to define the window.

Approach 3: Regular Expressions

Intuition We can use a regular expression to find all substrings consisting of 3 or more identical characters. The regex pattern (.)\1{2,} captures a character followed by the same character at least 2 more times.

Steps

• Construct the regex pattern (.)\1{2,}.
• Iterate through all matches found in the string.
• For each match, get the start index and end index (start index + length - 1) and add to the result list.

import re

class Solution:
    def largeGroupPositions(self, s: str) -> list[list[int]]:
        res = []
        # Pattern matches any char (.) followed by same char 2+ times
        for m in re.finditer(r'(.)\1{2,}', s):
            res.append([m.start(), m.end() - 1])
        return res

Complexity

• Time: O(n) in practice, though regex engines can have overhead.
• Space: O(1) auxiliary space.
• Notes: This approach is concise but may be less efficient than a manual scan due to regex engine overhead. It relies on language-specific regex support.