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"。

提示：

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

解题思路

解题思路

这道题目要求找到字符串中长度大于等于3的连续相同字符分组的位置区间。

双指针法（推荐解法）

使用双指针遍历字符串，时间复杂度O(n)，空间复杂度O(1)（不计输出空间）：

  1. 初始化两个指针：i 作为分组的起始位置，j 用于寻找分组的结束位置
  2. 对于每个位置 i，向右移动 j 直到遇到不同字符
  3. 计算当前分组长度 j - i，如果长度 >= 3，则将区间 [i, j-1] 加入结果
  4. 更新 i = j，继续处理下一个分组

实现要点

  • 内层while循环用于找到当前分组的结束位置
  • 注意区间是闭区间 [start, end]，所以结束位置是 j-1
  • 由于按顺序遍历，结果自然按起始位置递增排序

这种方法简洁高效，每个字符只被访问一次，是最优解法。

代码实现

class Solution {
public:
    vector<vector<int>> largeGroupPositions(string s) {
        vector<vector<int>> result;
        int n = s.length();
        int i = 0;
        
        while (i < n) {
            int j = i;
            while (j < n && s[j] == s[i]) {
                j++;
            }
            if (j - i >= 3) {
                result.push_back({i, j - 1});
            }
            i = j;
        }
        
        return result;
    }
};

class Solution:
    def largeGroupPositions(self, s: str) -> List[List[int]]:
        result = []
        n = len(s)
        i = 0
        
        while i < n:
            j = i
            while j < n and s[j] == s[i]:
                j += 1
            if j - i >= 3:
                result.append([i, j - 1])
            i = j
        
        return result

public class Solution {
    public IList<IList<int>> LargeGroupPositions(string s) {
        var result = new List<IList<int>>();
        int n = s.Length;
        int i = 0;
        
        while (i < n) {
            int j = i;
            while (j < n && s[j] == s[i]) {
                j++;
            }
            if (j - i >= 3) {
                result.Add(new List<int> { i, j - 1 });
            }
            i = j;
        }
        
        return result;
    }
}

/**
 * @param {string} s
 * @return {number[][]}
 */
var largeGroupPositions = function(s) {
    const result = [];
    const n = s.length;
    let i = 0;
    
    while (i < n) {
        let j = i;
        while (j < n && s[j]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n) - 每个字符只被访问一次
空间复杂度O(1) - 只使用常数额外空间（不计输出空间）

相关题目