830. Positions of Large Groups

Problem

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: []

Constraints:

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

Problem Summary

In a string s composed of lowercase letters, there are groups made up of consecutive identical characters. For example, in the string s = "abbxxxxzyy", there are groups such as "a", "bb", "xxxx", "z", and "yy". A group can be represented by an interval [start, end], where start and end respectively denote the starting and ending indices of the group. The "xxxx" group in the above example is represented by the interval [3,6]. We call any group containing three or more consecutive characters a large group.

Find the interval of each large group, sort them in increasing order by starting index, and return the result.

Solution Approach

• Easy problem. Use the sliding window idea: first expand the right boundary of the window to find the farthest reachable position with the same letter. Record the left and right boundaries. Then move the left boundary of the window to the previous right boundary. Repeat this process, expanding the right boundary of the window until the entire string has been scanned. In the end, all large group intervals that satisfy the requirements will be in the array.

Code

package leetcode

func largeGroupPositions(S string) [][]int {
	res, end := [][]int{}, 0
	for end < len(S) {
		start, str := end, S[end]
		for end < len(S) && S[end] == str {
			end++
		}
		if end-start >= 3 {
			res = append(res, []int{start, end - 1})
		}
	}
	return res
}