Algorithm
Problem Name: 830. Positions of Large Groups
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".
A group is identified by an interval [start, end], where start and end denote the start and end indices (inclusive) of the group. In the above example, "xxxx" has the interval [3,6].
A group is considered large if it has 3 or more characters.
Return the intervals of every large group sorted in increasing order by start index.
Example 1:
Input: s = "abbxxxxzzy"
Output: [[3,6]]
Explanation: "xxxx" is the only large group with start index 3 and end index 6.
Example 2:
Input: s = "abc" Output: [] Explanation: We have groups "a", "b", and "c", none of which are large groups.
Example 3:
Input: s = "abcdddeeeeaabbbcd" Output: [[3,5],[6,9],[12,14]] Explanation: The large groups are "ddd", "eeee", and "bbb".
Constraints:
1 <= s.length <= 1000scontains lowercase English letters only.
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
vector<vector<int>> largeGroupPositions(string S) {
vector < vector<int>>res;
int l = 0, r = 0, n = S.size();
while(l < n){
while(r < n && S[r] == S[l]) r++;
if(r - l >= 3) res.push_back({l, r - 1});
l = r;
}
return res;
}
};
Input
Output
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public List();
int idx = 0;
while (idx < s.length()) {
int startIdx = idx;
char c = s.charAt(idx);
while (idx < s.length() && s.charAt(idx) == c) {
idx++;
}
if (idx - startIdx >= 3) {
result.add(Arrays.asList(startIdx, idx - 1));
}
}
return result;
}
}
Input
Output
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const largeGroupPositions = function(S) {
if (S.length === 0) return [];
let prevChar = S[0];
let curChar = S[0];
let curStartIdx = 0;
let curCount = 1;
const res = [];
let tmpChar;
for (let i = 1; i < S.length; i++) {
tmpChar = S[i];
if (tmpChar === prevChar) {
curCount += 1;
} else {
if (curCount >= 3) {
res.push([curStartIdx, curStartIdx + curCount - 1]);
}
prevChar = S[i];
curStartIdx = i;
curCount = 1;
}
}
if (curCount >= 3) {
res.push([curStartIdx, curStartIdx + curCount - 1]);
}
return res;
};
console.log(largeGroupPositions("aaa"));
console.log(largeGroupPositions("abbxxxxzzy"));
console.log(largeGroupPositions("abcdddeeeeaabbbcd"));
Input
Output
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def largeGroupPositions(self, S):
res = []
l = r = 0
for i in range(1, len(S)):
if S[i] == S[i - 1]: r += 1
if r - l >= 2 and (S[i] != S[i - 1] or i == len(S) - 1): res.append([l, r])
if S[i] != S[i - 1]: l = r = i
return res
Input
Output
#5 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
namespace LeetCode
{
public class _0830_PositionsOfLargeGroups
{
public IList < IList<int>> LargeGroupPositions(string S)
{
var result = new List < IList<int>>();
var start = 0;
for (int i = 1; i < S.Length; i++)
if (S[i] != S[i - 1])
{
var len = i - start;
if (len >= 3)
result.Add(new int[] { start, i - 1 });
start = i;
}
if (S.Length - start > 2)
result.Add(new int[] { start, S.Length - 1 });
return result;
}
}
}
Input
Output