题目

难度：★★☆☆☆
类型：字符串

在一个由小写字母构成的字符串 S 中，包含由一些连续的相同字符所构成的分组。

例如，在字符串 S = "abbxxxxzyy" 中，就含有 "a", "bb", "xxxx", "z" 和 "yy" 这样的一些分组。

我们称所有包含大于或等于三个连续字符的分组为较大分组。找到每一个较大分组的起始和终止位置。

最终结果按照字典顺序输出。

示例

示例 1
输入: "abbxxxxzzy"
输出: [[3,6]]
解释: "xxxx" 是一个起始于 3 且终止于 6 的较大分组。

示例 2
输入: "abc"
输出: []
解释: "a","b" 和 "c" 均不是符合要求的较大分组。

示例 3
输入: "abcdddeeeeaabbbcd"
输出: [[3,5],[6,9],[12,14]]
说明: 1 <= S.length <= 1000

解答

较大分组：出现次数不小于3的连续字符串。我们可以通过一趟遍历实现：

1. 先判断特殊情况，如果字符串的长度小于3，那么一定不存在较大分组；

2. 初始化变量：
   （1）计数器count，表示到目前为止连续字符的数量；
   （2）起始位置start，与当前字符连续相同的最左侧字符所在位置；
   （2）结果变列表res，用来存放最终结果；

3. S的下标i是从1开始到len(S)-1的指针，i+1指向i后一个元素，如果S[i+1]=S[i]，则计数器+1，否则，该组子串遍历完毕，判断计数器是否不小于3，如果不小于3，当前组子串是较大分组，应该将起止位置添加到结果列表中。

4. 跳出循环后，还应该判断最后一个分组是否为较大分组。

class Solution:
    def largeGroupPositions(self, S):
        if len(S) < 3:
            return []
        res = []
        count = 1
        start = 0
        for i in range(1, len(S)):
            if S[i] == S[i-1]:
                count += 1
            else:
                if count >= 3:
                    res.append([start, start+count-1])
                start, count = i, 1

        if count >= 3:
            res.append([start, start + count - 1])
        return res

如有疑问或建议，欢迎评论区留言~