How to Find Positions of Large Groups using Two Pointer Algorithm?

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

Two Pointer Algorithm using Java

This problem is similar to the run-length compression coding, which we need to find the continuous group of characters. We use two pointers, i and j, where i is the beginning of the group and j is the end of the group until we reach the end of the string.

The following Java implementation uses Arrays.asList to convert a Integer array to a List of Integer.

The complexity is O(N) in both space and time. The first pointer i will jump to the end of the group i.e. second pointer j at the end of each group.

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>> res = new ArrayList();
        int i = 0, len = S.length();
        while (i < len) {
            int j = i + 1; 
            while (j < len && S.charAt(j) == S.charAt(i)) {
                j ++; // until the group ends
            }
            if (j - i + 1 > 3) {
                res.add( Arrays.asList(new Integer[]{i, j - 1}) );
            }
            i = j;
        }
        return res;
    }
}

class Solution {
    public List<List<Integer>> largeGroupPositions(String S) {
        List<List<Integer>> res = new ArrayList();
        int i = 0, len = S.length();
        while (i < len) {
            int j = i + 1; 
            while (j < len && S.charAt(j) == S.charAt(i)) {
                j ++; // until the group ends
            }
            if (j - i + 1 > 3) {
                res.add( Arrays.asList(new Integer[]{i, j - 1}) );
            }
            i = j;
        }
        return res;
    }
}

Two Pointer Algorithm using C++

C++ implementation will be slightly more concise as we can directly use {} to denote a vector.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    vector<vector<int>> largeGroupPositions(string S) {
        vector<vector<int>> res;
        int i = 0, len = S.size();
        while (i < len) {
            int j = i + 1;
            while (j < len && S[j] == S[i]) {
                j ++; // find end of the group
            }
            if (j - i + 1 > 3) {
                res.push_back( {i, j - 1} );
            }
            i = j;
        }
        return res;
    }
};

class Solution {
public:
    vector<vector<int>> largeGroupPositions(string S) {
        vector<vector<int>> res;
        int i = 0, len = S.size();
        while (i < len) {
            int j = i + 1;
            while (j < len && S[j] == S[i]) {
                j ++; // find end of the group
            }
            if (j - i + 1 > 3) {
                res.push_back( {i, j - 1} );
            }
            i = j;
        }
        return res;
    }
};

–EOF (The Ultimate Computing & Technology Blog) —