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

For example, a string likeS = "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

class Solution {
    public List<List<Integer>> largeGroupPositions(String S) {
        List<List<Integer>> ans = new ArrayList<>();
        if (S == null || S.length() == 0) return ans;

        PriorityQueue<List<Integer>> pq = new PriorityQueue<>((a, b) -> (a.get(0) - b.get(0)));

        int start = 0;
        while (start < S.length()){
            int end = start;
            while (end < S.length() && S.charAt(end) == S.charAt(start)){
                end++;
            }

            int len = end - start;
            if (len >= 3){
                List<Integer> temp = new ArrayList<>();
                temp.add(start);
                temp.add(end - 1);

                pq.offer(temp);
            }

            start = end;
        }

        while(!pq.isEmpty()){
            ans.add(pq.poll());
        }

        return ans;
    }
}