We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Positions of Large Groups

Number: 857

Difficulty: Easy

Paid? No

Companies: Google

Problem Description

Given a string of lowercase letters, consecutive identical characters form groups. A group is defined by its starting and ending indices. The task is to identify all "large groups," which are groups that contain at least 3 characters, and return their intervals sorted by the start index.

Key Insights

  • Traverse the string once, using a pointer to mark the start of the current group.
  • When the current character differs from the previous one, determine if the group length (i - group_start) is at least 3.
  • If it is, record the interval [group_start, i - 1].
  • Remember to check the final group after the loop ends.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string, as we scan the string once.
Space Complexity: O(1) extra space (excluding the output list), since only a few variables are used.

Solution

The solution iterates through the string while keeping track of the start index of each consecutive group. Each time a new character is encountered, it checks if the previous group length meets or exceeds 3. If so, it records the interval. The algorithm also handles the final group after the loop concludes.

Code Solutions

# Function to find positions of large groups in a string
def largeGroupPositions(s: str) -> list:
    # List to store the result intervals
    result = []
    # Starting index for the current group
    group_start = 0
    
    # Iterate through the string starting from the second character
    for i in range(1, len(s)):
        # When the current character is different, the group has ended
        if s[i] != s[i - 1]:
            # If the group length is at least 3, record its start and end indices
            if i - group_start >= 3:
                result.append([group_start, i - 1])
            # Update the start index for the new group
            group_start = i
    
    # Check the final group after the loop ends
    if len(s) - group_start >= 3:
        result.append([group_start, len(s) - 1])
    
    return result

# Example usage:
print(largeGroupPositions("abbxxxxzzy"))  # Expected Output: [[3,6]]
← Back to All Questions