Sponsored
Sponsored
This approach involves iterating through the string to detect groups of consecutive characters. We maintain a start index for the current group and check whenever a character changes. If the length of a group is 3 or more, we record the start and end indices.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n) for storing the result.
1
2#include <vector>
3#include <string>
4using namespace std;
5
6vector<vector<int>> largeGroupPositions(string s) {
7 vector<vector<int>> result;
8 int start = 0, n = s.size();
9 for (int i = 1; i <= n; ++i) {
10 if (i == n || s[i] != s[start]) {
11 if (i - start >= 3) {
12 result.push_back({start, i - 1});
13 }
14 start = i;
15 }
16 }
17 return result;
18}
19In this C++ solution, we iterate through the string with a single loop. A vector of vectors is used to store the resulting intervals of large groups.
The two-pointer technique is another efficient way to solve this problem. The idea is to have a slow pointer marking the start of the group and a fast pointer iterating through the string. When the character at the fast pointer changes or reaches the end, check the length of the group.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n) for storing the result.
1using System;
using System.Collections.Generic;
public class Solution {
public IList<IList<int>> LargeGroupPositions(string s) {
List<IList<int>> result = new List<IList<int>>();
int slow = 0;
for (int fast = 0; fast < s.Length; fast++) {
if (fast == s.Length - 1 || s[fast] != s[fast + 1]) {
if (fast - slow + 1 >= 3) {
result.Add(new List<int> { slow, fast });
}
slow = fast + 1;
}
}
return result;
}
}
This C# implementation uses two pointers to achieve efficient operation, setting `slow` to mark group start, while `fast` iterates, appending results accordingly.