Domain 1EasyCORE

Positions of Large Groups

The problem requires identifying consecutive groups of the same character in a string and returning the intervals (start and end indices) of those groups that have 3 or more characters. The input is a single string `s` containing lowercase English letters only. The output should be a list of lists, where each inner list contains two integers representing the start and end indices of a large group.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array

830. Positions of Large Groups

Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 1
Acceptance rate: 50.5%


Problem Breakdown

The problem requires identifying consecutive groups of the same character in a string and returning the intervals (start and end indices) of those groups that have 3 or more characters. The input is a single string s containing lowercase English letters only. The output should be a list of lists, where each inner list contains two integers representing the start and end indices of a large group.

Inputs:

  • A string s of lowercase letters.

Outputs:

  • A list of intervals [start, end] for each large group.

Implicit Constraints or Tricky Edge Cases:

  • The string can be empty.
  • All characters in the string are lowercase English letters.
  • Groups with fewer than 3 characters should not be included in the output.

Intuition

A brute-force approach would involve iterating through the string and checking every possible substring to see if it forms a large group. This would be inefficient, especially for longer strings, as it would result in a time complexity of O(n^2).

The key insight is to use a two-pointer technique to efficiently identify groups of consecutive characters. By maintaining a start pointer and an end pointer, we can traverse the string once (O(n) time complexity), identifying each group and checking its length.

Approach

  1. Initialize an empty list result to store the intervals of large groups.
  2. Use two pointers, start and end, both initialized to 0.
  3. Traverse the string using a while loop until end reaches the end of the string:
    • Increment end while the character at end is the same as the character at start.
    • Once a different character is encountered or the end of the string is reached, check if the length of the group (i.e., end - start) is 3 or more.
    • If it is, append the interval [start, end-1] to the result list.
    • Set start to end to begin checking the next group.
  4. Return the result list.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the string. We traverse the string once with two pointers.
  • Space Complexity: O(1) for the additional variables used, excluding the space required for the output list.

Solution

def largeGroupPositions(s: str) -> List[List[int]]:
    result = []
    start = 0
    end = 0
    
    while end < len(s):
        # Move end pointer to the right as long as characters are the same
        while end < len(s) and s[end] == s[start]:
            end += 1
        
        # Check if the group is large
        if end - start >= 3:
            result.append([start, end - 1])
        
        # Move start pointer to the position of end
        start = end
    
    return result

Edge Cases Handled

  • Empty String: The function will return an empty list as there are no groups in an empty string.
  • Single Character Groups: Groups with fewer than 3 characters are not added to the result.
  • All Characters Same: If all characters in the string are the same, the entire string is considered a large group if its length is 3 or more.