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 <stdio.h>
3#include <stdlib.h>
4#include <string.h>
5
6int** largeGroupPositions(char* s, int* returnSize, int** returnColumnSizes) {
7 int n = strlen(s);
8 int** result = (int**)malloc(n * sizeof(int*));
9 *returnColumnSizes = (int*)malloc(n * sizeof(int));
10 *returnSize = 0;
11 int start = 0;
12 for (int i = 1; i <= n; i++) {
13 if (i == n || s[i] != s[start]) {
14 if (i - start >= 3) {
15 result[*returnSize] = (int*)malloc(2 * sizeof(int));
16 result[*returnSize][0] = start;
17 result[*returnSize][1] = i - 1;
18 (*returnColumnSizes)[*returnSize] = 2;
19 (*returnSize)++;
20 }
21 start = i;
22 }
23 }
24 return result;
25}
26The function iterates through the string, marking the start of a group. Whenever a character change is detected, it checks the size of the group. Groups of size 3 or more are considered 'large', and their start and end indices are added to the results.
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 JavaScript and the two-pointer approach, this solution efficiently manages group detection and results appending based on character transitions identified by `fast`.