830. 较大分组的位置#

题目描述#

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

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

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

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

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

示例 1：

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

示例 2：

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

示例 3：

1
输入：s = "abcdddeeeeaabbbcd"
2
输出：[[3,5],[6,9],[12,14]]

提示：

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

解题思路#

核心思想#

用分组循环把字符串按连续相同字符分成段，段长 >= 3 的即为较大分组，把 [i, j] 加入结果。由于各段天然按下标递增排列，结果无需额外排序。

分组示意（s = “abcdddeeeeaabbbcd”）：

1
a | b | c | ddd | eeee | aa | bbb | c | d
2
              [3,5]  [6,9]      [12,14]

算法步骤#

令 i = 0，初始化结果列表 res。
当 i < n 时：
- j = i，扩展 while j+1 < n and s[j+1] == s[i]；
- 若 j - i + 1 >= 3，把 [i, j] 加入 res；
- i = j + 1。
返回 res。

逐步举例#

以 s = "abcdddeeeeaabbbcd" 为例：

段	区间	长度	是否 ≥3
a	[0,0]	1	否
b	[1,1]	1	否
c	[2,2]	1	否
ddd	[3,5]	3	✅
eeee	[6,9]	4	✅
aa	[10,11]	2	否
bbb	[12,14]	3	✅

结果为 [[3,5],[6,9],[12,14]]。

复杂度分析#

时间复杂度：O(N)，单次线性扫描。
空间复杂度：O(1)（不计输出结果空间）。

代码实现#

1
from typing import List
2

3

4
class Solution:
5
    def largeGroupPositions(self, s: str) -> List[List[int]]:
6
        res = []
7
        n = len(s)
8
        i = 0
9
        while i < n:
10
            j = i
11
            while j + 1 < n and s[j + 1] == s[i]:
12
                j += 1
13
            if j - i + 1 >= 3:
14
                res.append([i, j])
15
            i = j + 1
16
        return res

1
import sys
2
from pathlib import Path
3

4
sys.path.insert(0, str(Path(__file__).parent))
5
import unittest
6

7
from solution import Solution
8

9

10
class TestSolution(unittest.TestCase):
11
    def test_example1(self):
12
        self.assertEqual(Solution().largeGroupPositions("abbxxxxzzy"), [[3, 6]])
13

14
    def test_example2(self):
15
        self.assertEqual(Solution().largeGroupPositions("abc"), [])
16

17
    def test_example3(self):
18
        self.assertEqual(Solution().largeGroupPositions("abcdddeeeeaabbbcd"),
19
                         [[3, 5], [6, 9], [12, 14]])
20

21

22
if __name__ == '__main__':
23
    unittest.main()