LeetCode 830 - Positions of Large Groups

LeetCode Problem 830

Difficulty: 🟢 Easy
Topics: String

Solution

Problem Understanding

The problem asks us to identify all large groups in a given string and return their positions as intervals.

A group is a sequence of consecutive identical characters. For example, in the string abbxxxxzzy, the groups are:

• "a"
• "bb"
• "xxxx"
• "zz"
• "y"

Each group can be represented by its starting index and ending index, inclusive. For example, "xxxx" starts at index 3 and ends at index 6, so its interval is [3,6].

A group is considered large if it contains at least 3 consecutive identical characters. Our goal is to scan the string and return all such intervals, sorted by increasing start index.

The input is a single string s consisting only of lowercase English letters. The output is a list of intervals, where each interval represents one large group.

The constraints are relatively small:

• 1 <= s.length <= 1000
• Only lowercase English letters appear

Since the input size is small, even less efficient approaches would technically work. However, this problem naturally admits a simple and optimal linear-time solution.

Several edge cases are important to recognize upfront. A string may contain no large groups at all, such as "abc". A large group might occur at the very beginning or end of the string, which can expose off-by-one bugs. The entire string might consist of a single repeated character, such as "aaaaa", meaning we must correctly identify a group that spans the full range of indices. Another subtle case is when multiple large groups appear consecutively, requiring careful tracking of boundaries.

Approaches

Brute Force Approach

A brute force solution would examine every possible substring and determine whether it forms a valid large group.

For each starting position, we could expand outward while characters remain the same and measure the group length. After identifying a group, we would check whether its size is at least 3 and append its interval if necessary.

Although this approach still works within the constraints, it may repeatedly inspect the same characters multiple times. In the worst case, such as a string with repeated characters, nested scanning can introduce unnecessary overhead.

The brute force approach is correct because every possible consecutive group is explicitly inspected, ensuring no large group is missed. However, it is inefficient because repeated comparisons are redundant.

Optimal Approach, Single Pass Two Pointer Scan

The key observation is that groups are naturally contiguous, meaning we only need to traverse the string once while tracking the current group's boundaries.

Instead of repeatedly rescanning characters, we maintain a pointer marking the start of the current group. We continue moving through the string until the character changes. At that point, we know the exact size of the group and can determine whether it qualifies as large.

This works efficiently because every character belongs to exactly one group, so each character is visited only once.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Repeatedly scans overlapping portions of the string
Optimal	O(n)	O(1) excluding output	Single traversal, processes each character once

Algorithm Walkthrough

1. Initialize an empty result list to store intervals of large groups.
2. Create a variable start to mark the beginning of the current group. Initially, this is 0 because the first character starts the first group.
3. Traverse the string using an index i starting from 1.
4. At each position, compare s[i] with s[i - 1].

• If they are the same, the current group continues.
• If they differ, the previous group has ended.

5. When a group ends, compute its size as:

length = i - start

If the length is at least 3, append [start, i - 1] to the result. 6. Reset start = i to begin tracking the next group. 7. After finishing the loop, handle the final group separately because the loop ends without triggering a character change. 8. Compute the last group's length. If it is at least 3, add its interval. 9. Return the result list.

Why it works

The algorithm maintains the invariant that start always points to the beginning of the current consecutive group. Whenever a character change occurs, the current group is fully known and can be evaluated exactly once. Since every character belongs to exactly one group and every group is checked precisely when it ends, the algorithm correctly identifies all large groups without missing or duplicating any intervals.

Python Solution

from typing import List

class Solution:
    def largeGroupPositions(self, s: str) -> List[List[int]]:
        result = []
        start = 0

        for i in range(1, len(s)):
            if s[i] != s[i - 1]:
                if i - start >= 3:
                    result.append([start, i - 1])
                start = i

        if len(s) - start >= 3:
            result.append([start, len(s) - 1])

        return result

The implementation begins by creating an empty result list and initializing start to 0, representing the beginning of the current group.

The for loop iterates through the string from index 1 onward. At each step, the current character is compared with the previous one. If the characters differ, we know the current group has ended. We then compute the group's length using i - start. If the group length is at least 3, we append its interval to the result.

After processing the ended group, start is updated to i, beginning a new group.

Once the loop completes, there is still one unprocessed group remaining, the final group in the string. Since no character change occurs after the last character, we explicitly check it after the loop and append it if large enough.

Finally, the result list is returned.

Go Solution

func largeGroupPositions(s string) [][]int {
	result := [][]int{}
	start := 0

	for i := 1; i < len(s); i++ {
		if s[i] != s[i-1] {
			if i-start >= 3 {
				result = append(result, []int{start, i - 1})
			}
			start = i
		}
	}

	if len(s)-start >= 3 {
		result = append(result, []int{start, len(s) - 1})
	}

	return result
}

The Go implementation follows the same logic as the Python solution. A slice of integer slices, [][]int, is used to store intervals.

One Go-specific detail is slice initialization. We initialize result as an empty slice rather than nil, though either would work in LeetCode. Appending intervals is done using append.

There are no concerns about integer overflow because the maximum string length is only 1000. String indexing in Go accesses bytes, which is safe here because the problem guarantees lowercase English letters only.

Worked Examples

Example 1

Input:

s = "abbxxxxzzy"

i	Character	Previous	start	Action	Result
1	b	a	0	Group ends, size = 1	[]
2	b	b	1	Continue group	[]
3	x	b	1	Group ends, size = 2	[]
4	x	x	3	Continue group	[]
5	x	x	3	Continue group	[]
6	x	x	3	Continue group	[]
7	z	x	3	Group ends, size = 4, add [3,6]	[[3,6]]
8	z	z	7	Continue group	[[3,6]]
9	y	z	7	Group ends, size = 2	[[3,6]]

Final group "y" has size 1, so nothing is added.

Output:

[[3,6]]

Example 2

Input:

s = "abc"

i	Character	Previous	start	Action	Result
1	b	a	0	Group size = 1	[]
2	c	b	1	Group size = 1	[]

Final group "c" has size 1.

Output:

[]

Example 3

Input:

s = "abcdddeeeeaabbbcd"

Group	Start	End	Length	Large?
a	0	0	1	No
b	1	1	1	No
c	2	2	1	No
ddd	3	5	3	Yes
eeee	6	9	4	Yes
aa	10	11	2	No
bbb	12	14	3	Yes
c	15	15	1	No
d	16	16	1	No

Output:

[[3,5],[6,9],[12,14]]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is processed exactly once
Space	O(1)	Only a few variables are used, excluding output storage

The algorithm performs a single pass through the string. Every character is visited once, and each group is evaluated exactly one time when it ends. This gives linear time complexity, O(n).

The extra space usage is constant because only a few tracking variables are maintained. The result list is not counted toward auxiliary space complexity because it is required for the output.

Test Cases

sol = Solution()

# Provided examples
assert sol.largeGroupPositions("abbxxxxzzy") == [[3, 6]]  # one large group
assert sol.largeGroupPositions("abc") == []  # no large groups
assert sol.largeGroupPositions("abcdddeeeeaabbbcd") == [[3, 5], [6, 9], [12, 14]]  # multiple groups

# Boundary cases
assert sol.largeGroupPositions("a") == []  # single character
assert sol.largeGroupPositions("aa") == []  # group smaller than 3
assert sol.largeGroupPositions("aaa") == [[0, 2]]  # exact size 3

# Entire string is one large group
assert sol.largeGroupPositions("aaaaa") == [[0, 4]]  # whole string

# Large group at beginning
assert sol.largeGroupPositions("aaab") == [[0, 2]]  # prefix group

# Large group at end
assert sol.largeGroupPositions("baaa") == [[1, 3]]  # suffix group

# Multiple adjacent groups
assert sol.largeGroupPositions("aaabbbccc") == [[0, 2], [3, 5], [6, 8]]  # several groups

# Mixed group sizes
assert sol.largeGroupPositions("aabbbccdddd") == [[2, 4], [7, 10]]  # mixed valid and invalid groups

# No repeated characters
assert sol.largeGroupPositions("abcdef") == []  # all single-character groups

Test	Why
"abbxxxxzzy"	Validates a single large group
"abc"	Ensures no false positives
"abcdddeeeeaabbbcd"	Tests multiple large groups
"a"	Smallest input size
"aa"	Group size below threshold
"aaa"	Exact threshold case
"aaaaa"	Entire string is one group
"aaab"	Large group at start
"baaa"	Large group at end
"aaabbbccc"	Consecutive large groups
"aabbbccdddd"	Mixed group sizes
"abcdef"	No repeated characters

Edge Cases

Entire String Is One Large Group

A common source of bugs occurs when the entire string contains the same character, such as "aaaaa". Since no character change ever occurs, a naive implementation might forget to process the final group. This implementation handles that correctly with an explicit post-loop check, producing [[0,4]].

Large Group at the End of the String

Cases like "baaa" are tricky because the last group does not naturally terminate through a character change. Without a final check, the group "aaa" could be missed entirely. The implementation explicitly evaluates the final segment after traversal to avoid this issue.

No Large Groups Exist

Inputs such as "abc" contain only groups of size 1. A careless implementation might accidentally include intervals due to incorrect comparison logic or off-by-one mistakes. This implementation only appends intervals when the group size is at least 3, ensuring an empty list is returned correctly.

Groups Exactly at the Threshold

A group of exactly length 3, such as "aaa", must count as large. Off-by-one errors often occur when using > instead of >=. This implementation explicitly checks >= 3, ensuring threshold cases are handled properly.