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

Call a group large if it has 3 or more characters.  We would like the starting and ending positions of every large group.

The final answer should be in lexicographic order.


Example 1:

Input: "abbxxxxzzy"
Output: [[3,6]]
Explanation: "xxxx" is the single large group with starting  3 and ending positions 6.

Example 2:

Input: "abc"
Output: []
Explanation: We have "a","b" and "c" but no large group.

Example 3:

Input: "abcdddeeeeaabbbcd"
Output: [[3,5],[6,9],[12,14]]


Note:
1 <= S.length <= 1000


Solution:

This problem is similar to count and say.

We use two pointers to iterate the string.

The left pointer always point to the start of the character.

The right pointer goes right until it finds a different character and then check the distance between the left pointer and right pointer - 1.

Both left and right pointers only go one direction. Thus the time complexity is O(n).


Code:

class Solution {
    public List<List<Integer>> largeGroupPositions(String S) {
        List<List<Integer>> result = new ArrayList<>();
        int left = 0;
        int right = 0;
        while (left < S.length()) {
            while (right < S.length() && S.charAt(left) == S.charAt(right)) {
                right++;
            }
            if (right - left >= 3) {
                result.add(Arrays.asList(new Integer[]{left, right - 1}));
            }
            left = right;
        }
        return result;
    }
}