Welcome to Subscribe On Youtube
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.
-
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; } } ############ class Solution { public List<List<Integer>> largeGroupPositions(String s) { int n = s.length(); int i = 0; List<List<Integer>> ans = new ArrayList<>(); while (i < n) { int j = i; while (j < n && s.charAt(j) == s.charAt(i)) { ++j; } if (j - i >= 3) { ans.add(Arrays.asList(i, j - 1)); } i = j; } return ans; } }
-
// 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: str) -> List[List[int]]: i, n = 0, len(s) ans = [] while i < n: j = i while j < n and s[j] == s[i]: j += 1 if j - i >= 3: ans.append([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
-
func largeGroupPositions(s string) [][]int { i, n := 0, len(s) ans := [][]int{} for i < n { j := i for j < n && s[j] == s[i] { j++ } if j-i >= 3 { ans = append(ans, []int{i, j - 1}) } i = j } return ans }