较大分组的位置

难度: Easy

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

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

分组可以用区间 [start, end] 表示，其中 start 和 end 分别表示该分组的起始和终止位置的下标。上例中的 "xxxx" 分组用区间表示为 [3,6] 。

我们称所有包含大于或等于三个连续字符的分组为 较大分组 。

找到每一个 较大分组 的区间，按起始位置下标递增顺序排序后，返回结果。

示例 1：

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

示例 2：

输入：s = "abc"
输出：[]
解释："a","b" 和 "c" 均不是符合要求的较大分组。

示例 3：

输入：s = "abcdddeeeeaabbbcd"
输出：[[3,5],[6,9],[12,14]]
解释：较大分组为 "ddd", "eeee" 和 "bbb"

示例 4：

输入：s = "aba"
输出：[]

提示：

1 <= s.length <= 1000
s 仅含小写英文字母

Submission

运行时间: 22 ms

内存: 16.0 MB

class Solution:
    def largeGroupPositions(self, s: str) -> List[List[int]]:
        res = []
        n = len(s)
        # i = -1
        i = 0
        # now_char = s[0]
        # left = 0
        # right = 0
        now_char = None
        left = right = 0
        while i < n:
            if now_char is None:
                now_char = s[i]
            elif s[i] == now_char:
                right += 1
            else:
                # res.append([left, right])
                if right - left + 1 >= 3:
                    res.append([left, right])
                left = right = i
                now_char = s[i]
            i += 1
        if right - left + 1 >= 3:
            res.append([left, right])
        return res

Explain

这个题解采用了双指针的思路。使用 left 和 right 两个指针分别表示当前分组的起始和结束位置。遍历字符串，如果当前字符与前一个字符相同，则 right 指针向右移动；否则，判断 left 和 right 之间的长度是否大于等于3，如果是则将 [left, right] 加入结果，并将 left 和 right 都置为当前位置 i，表示开始一个新的分组。最后再判断最后一个分组是否满足条件。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def largeGroupPositions(self, s: str) -> List[List[int]]:
        res = []
        n = len(s)
        i = 0
        now_char = None
        left = right = 0
        while i < n:
            if now_char is None:
                now_char = s[i]  # 初始化当前字符
            elif s[i] == now_char:
                right += 1  # 如果当前字符与前一个字符相同，右指针右移
            else:
                if right - left + 1 >= 3:
                    res.append([left, right])  # 如果当前分组长度大于等于3，加入结果
                left = right = i  # 开始新的分组，左右指针都指向当前位置
                now_char = s[i]  # 更新当前字符
            i += 1  # 遍历下一个字符
        if right - left + 1 >= 3:
            res.append([left, right])  # 处理最后一个分组
        return res

Explore

在代码中，处理最后一个字符后的边界情况是通过在循环结束后再次检查`right - left + 1 >= 3`来实现的。如果循环结束时最后一个分组的长度满足大于等于3的条件，则将这个分组的起始和结束位置添加到结果列表中。这样做确保了即使最后一个分组也能被正确处理。

代码中的`now_char = s[i]`用于更新当前正在检查的字符。当遇到与`now_char`不同的字符时，这表示前一个字符的连续序列已结束，并开始一个新的字符序列。因此，这种更新方式不会导致连续字符错误地断开，而是恰当地标记了连续字符序列的结束，并且正确地开始新的分组。

在判断`if right - left + 1 >= 3`时，`right - left + 1`计算的是当前分组的长度。这里的'1'是因为索引是从0开始的，所以需要加1来得到正确的元素数量。例如，如果`left`和`right`分别是0和2，实际上包括的元素是索引为0, 1, 2的三个元素，总共3个元素。选择这个条件是因为题目中定义较大分组为长度至少为3的连续相同字符的序列。

在代码中，`right`指针在遇到连续字符时递增，并且在添加到结果列表时，`right`自然就是当前分组的结束位置。由于处理逻辑保证了每次更新分组时`right`都指向当前分组的最后一个字符，所以当满足条件被添加到结果列表时，`right`已正确表示了分组的结束位置。