1. 题目描述

在一个由小写字母构成的字符串 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]]
  3. 解释：较大分组为 "ddd", "eeee" 和 "bbb"

示例 4：

  1. 输入：s = "aba"
  2. 输出：[]

提示：

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

    2. 解题思路

    （1）直接遍历
    对于这道题目，可以直接一趟进行遍历。初始化一个num，用来保存当前分组的长度。每次增加一个相同字符，num就加一。如果下一个字符和当前字符不同，或者是已经遍历到字符串尾部，就说明相同的字符已经遍历完了。如果此时num满足较大分组的条件，就其加入到结果中。

复杂度分析：

  • 时间复杂度：O(n)，其中 n 是字符串的长度，只需要遍历一次该数组。
  • 空间复杂度：O(1)，只需要常数的空间来保存若干变量，返回值不计入空间复杂度。

（2）双指针
除了直接遍历之外，我们还可以使用双指针来实现这个题目。

  • 初始化两个指针 left 和 right 分比为0和1
  • 只要 left 和 right 值相等，就向右移动 right 指针
  • 如果 left 和 right 值不相等，就计算前面的相同字符的个数，判断个数是否大于等于3：当满足条件时，将对应的起始索引位置添加到结果列表中，维护更新 left = right；否则，直接更新 left = right。

复杂度分析：

  • 时间复杂度：O(n)，其中 n 是字符串的长度，只需要遍历一次该数组。

  • 空间复杂度：O(1)，只需要常数的空间来保存若干变量，返回值不计入空间复杂度。

    3. 代码实现

    （1）直接遍历

    1. /**
    2. * @param {string} s
    3. * @return {number[][]}
    4. */
    5. var largeGroupPositions = function(s) {
    6.   let res = [], num = 1, len = s.length
    8.   for(let i = 0; i <= len; i++){
    9.       if(i === len - 1 || s[i] !== s[i + 1]){
    10.           if(num >= 3){
    11.               res.push([i - num + 1, i])
    12.           }
    13.           num = 1
    14.       }else{
    15.           num++
    16.       }
    17.   }
    18.   return res
    19. };

    （2）双指针

    1. /**
    2. * @param {string} s
    3. * @return {number[][]}
    4. */
    5. var largeGroupPositions = function(s) {
    6.   let res = [], len = s.length, left = 0, right = 1
    8.   while(right <= len){
    9.       if(right === len || s[left] !== s[right]){
    10.           if(right - left >= 3){
    11.               res.push([left, right - 1])
    12.           }
    13.           left = right
    14.       }
    15.       right += 1
    16.   }
    17.   return res
    18. };

    4. 提交结果

    （1）直接遍历
    image.png
    （2）双指针
    image.png