跳至主要內容

0830. 较大分组的位置

ITCharge大约 2 分钟

0830. 较大分组的位置open in new window

  • 标签:字符串
  • 难度:简单

题目链接

题目大意

描述:给定由小写字母构成的字符串 ss。字符串 ss 包含一些连续的相同字符所构成的分组。

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

说明

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

示例

  • 示例 1:
输入:s = "abbxxxxzzy"
输出:[[3,6]]
解释:"xxxx" 是一个起始于 3 且终止于 6 的较大分组。
  • 示例 2:
输入:s = "abc"
输出:[]
解释:"a","b""c" 均不是符合要求的较大分组。

解题思路

思路 1:简单模拟

遍历字符串 ss,统计出所有大于等于 33 个连续字符的子字符串的开始位置与结束位置。具体步骤如下:

  1. cnt=1cnt = 1,然后从下标 11 位置开始遍历字符串 ss
    1. 如果 s[i1]==s[i]s[i - 1] == s[i],则令 cntcnt11
    2. 如果 s[i1]s[i]s[i - 1] \ne s[i],说明出现了不同字符,则判断之前连续字符个数 cntcnt 是否大于等于 33
    3. 如果 cnt3cnt \ge 3,则将对应包含 cntcnt 个连续字符的子字符串的开始位置与结束位置存入答案数组中。
    4. cnt=1cnt = 1,重新开始记录连续字符个数。
  2. 遍历完字符串 ss,输出答案数组。

思路 1:代码

class Solution:
    def largeGroupPositions(self, s: str) -> List[List[int]]:
        res = []
        cnt = 1
        size = len(s)
        for i in range(1, size):
            if s[i] == s[i - 1]:
                cnt += 1
            else:
                if cnt >= 3:
                    res.append([i - cnt, i - 1])
                cnt = 1
        if cnt >= 3:
            res.append([size - cnt, size - 1])
        return res

思路 1:复杂度分析

  • 时间复杂度O(n)O(n)
  • 空间复杂度O(1)O(1)