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; } } -
// 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; } }; -
class Solution: def largeGroupPositions(self, S): """ :type S: str :rtype: List[List[int]] """ groups = [] before_index, before_char = 0, S[0] for i, s in enumerate(S): if s != before_char: if i - before_index >= 3: groups.append([before_index, i - 1]) before_index = i before_char = s if i - before_index >= 2: groups.append([before_index, i]) return groups