Formatted question description: https://leetcode.ca/all/830.html
830. Positions of Large Groups (Easy)
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
Companies:
Adobe
Related Topics:
Array
Solution 1.
// OJ: https://leetcode.com/problems/positions-of-large-groups/
// Time: O(N)
// Space: O(1)
class Solution {
public:
vector<vector<int>> largeGroupPositions(string S) {
vector<vector<int>> ans;
for (int N = S.size(), i = 0; i < N;) {
int j = i + 1;
while (j < N && S[j] == S[i]) ++j;
if (j - i >= 3) ans.push_back({ i, j - 1 });
i = j;
}
return ans;
}
};
Java
class Solution {
public List<List<Integer>> largeGroupPositions(String S) {
List<List<Integer>> largeGroupPositions = new ArrayList<List<Integer>>();
if (S.length() < 3)
return largeGroupPositions;
int begin = 0;
char prev = S.charAt(0);
int length = S.length();
for (int i = 1; i < length; i++) {
char c = S.charAt(i);
if (c != prev) {
if (i - begin >= 3) {
int end = i - 1;
List<Integer> largeGroupPosition = new ArrayList<Integer>();
largeGroupPosition.add(begin);
largeGroupPosition.add(end);
largeGroupPositions.add(largeGroupPosition);
}
begin = i;
}
prev = c;
}
if (length - begin >= 3) {
int end = length - 1;
List<Integer> largeGroupPosition = new ArrayList<Integer>();
largeGroupPosition.add(begin);
largeGroupPosition.add(end);
largeGroupPositions.add(largeGroupPosition);
}
return largeGroupPositions;
}
}