830.较大分组的位置

(Updated: )
LeetCode

Q

在一个由小写字母构成的字符串 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”
输出：[]

A

双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public List<List<Integer>> largeGroupPositions(String s) {
       s = s + "A";
        List<List<Integer>> answer = new ArrayList<>();
        //指针i
        for(int i=0;i<s.length();i++){
            //指针j,当指针i停留在字符串s的第i个字符位置时,移动指针j
            for(int j=i+1;j<s.length();j++){
                //若出现了连续2位相等的情况
                if(s.charAt(i) == s.charAt(j)){
                    //若出现了连续3位以上相等且连续有中断,记录当前i,j指针的位置,并将i指针移动到当前分组的末尾位置
                    if(j-i>=2&&s.charAt(i)!=s.charAt(j+1)){
                        // List<Integer> group = new ArrayList<>();
                        // group.add(i);
                        // group.add(j);
                        answer.add(Arrays.asList(i,j));
                        i= j+1;
                    }
                }else {
                    //若只是连续2位相等,移动i指针,回退j指针
                    i++;
                    j--;
                }
            }
        }
        return answer;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public List<List<Integer>> largeGroupPositions(String s) {
        List<List<Integer>> ans = new ArrayList();
        int i = 0, N = s.length(); // i is the start of each group
        for (int j = 0; j < N; ++j) {
            if (j == N-1 || s.charAt(j) != s.charAt(j+1)) {
				//双指针法，判断条件更好更完善，不相等或者到达尾端时
                // Here, [i, j] represents a group.
                if (j-i+1 >= 3)
                    ans.add(Arrays.asList(new Integer[]{i, j}));
				//i从j的下一个作为起始位置，相当于固定i，用j去遍历
                i = j + 1;                                           
            }
        }
        return ans;
    }
}

  • 时间复杂度
    O(N(N-1)/2) N为字符串长度

  • 空间复杂度
    O(1)

一次遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
    public List<List<Integer>> largeGroupPositions(String s) {
        // 1. 初始化
        List<List<Integer>> res = new ArrayList<>();                // 结果集
        int n   = s.length();                                       // 字符串长度
        int num = 1;                                                // 用于记录分组长度 

        // 2. 一次遍历该字符串
        for(int i = 0;i < n;i++){
            // 2.1 如果下一个字符与当前字符不同,或者已经枚举到字符串尾部,就说明当前字符为当前分组的尾部
            if(i == n - 1 || s.charAt(i) != s.charAt(i + 1)){
                if(num >= 3){                                       // 如果分组长度达到3
                    res.add(Arrays.asList(i - num + 1,i));          // 记录结果
                }   
                num = 1;                                            // 重置分组长度
            // 2.2 字符重复的情况
            }else{
                num++;                                              // ++字符分区长度
            }
        }
        // 3. 返回结果集
        return res;                                                
    }
}

  • 思路
    遍历该序列，并记录当前分组的长度。如果下一个字符与当前字符不同，或者已经枚举到字符串尾部，就说明当前字符为当前分组的尾部。每次找到当前分组的尾部时，如果该分组长度达到 3，我们就将其加入答案。

  • 时间复杂度
    O(N) N为字符串长度

  • 空间复杂度
    O(1)