[LeetCode] 830. Positions of Large Groups

In a string s of lowercase letters, these letters form consecutive groups of the same character.

For example, a string like s = "abbxxxxzyy" has the groups "a""bb""xxxx""z", and "yy".

A group is identified by an interval [start, end], where start and end denote the start and end indices (inclusive) of the group. In the above example, "xxxx" has the interval [3,6].

A group is considered large if it has 3 or more characters.

Return the intervals of every large group sorted in increasing order by start index.

Example 1:

Input: s = "abbxxxxzzy"
Output: [[3,6]]
Explanation: "xxxx" is the only large group with start index 3 and end index 6.

Example 2:

Input: s = "abc"
Output: []
Explanation: We have groups "a", "b", and "c", none of which are large groups.

Example 3:

Input: s = "abcdddeeeeaabbbcd"
Output: [[3,5],[6,9],[12,14]]
Explanation: The large groups are "ddd", "eeee", and "bbb".

Example 4:

Input: s = "aba"
Output: []

Constraints:

  • 1 <= s.length <= 1000
  • s contains lower-case English letters only.

较大分组的位置。

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

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

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

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

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/positions-of-large-groups
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

这道题的题意简化一下就是找input字符串中长度大于等于3的子串,子串里面都是相同字母,输出这些子串的[start, end]。思路是two pointer。注意当两个指针指向的字母不同的时候,要立即将左指针放到右指针的位置上,再进行下面的扫描。

时间O(n)

空间O(n) - output

Java实现

 1 class Solution {
 2     public List<List<Integer>> largeGroupPositions(String s) {
 3         List<List<Integer>> res = new ArrayList<>();
 4         int i = 0;
 5         for (int j = 1; j < s.length(); j++) {
 6             while (j < s.length() && s.charAt(i) == s.charAt(j)) {
 7                 j++;
 8             }
 9             if (j - i >= 3) {
10                 res.add(Arrays.asList(i, j - 1));
11             }
12             i = j;
13         }
14         return res;
15     }
16 }

 

LeetCode 题目总结

上一篇:JAVA使用for循环会重复调用list.size()吗4


下一篇:JAVA使用for循环会重复调用list.size()吗7