Sponsored
Sponsored
This approach utilizes a stack data structure to track characters and their counts. As we iterate through the string, we push characters with their current counts on the stack. When the count of the top character in the stack reaches k, we pop the character from the stack to simulate removal of duplicates.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n), for the stack and auxiliary storage.
1#include <stdio.h>
2#include <string.h>
3#include <stdlib.h>
4
5char* removeDuplicates(char* s, int k) {
6 int len = strlen(s), top = 0;
7 char *res = (char *)malloc((len + 1) * sizeof(char));
8 int *count = (int *)malloc(len * sizeof(int));
9
10 for (int i = 0; i < len; i++) {
11 if (top != 0 && res[top - 1] == s[i]) {
12 count[top - 1]++;
13 } else {
14 res[top] = s[i];
15 count[top] = 1;
16 top++;
17 }
18 if (count[top - 1] == k) {
19 top--;
20 }
21 }
22 res[top] = '\0';
23 free(count);
24 return res;
25}
26
27int main() {
28 char s[] = "deeedbbcccbdaa";
29 int k = 3;
30 char *result = removeDuplicates(s, k);
31 printf("%s\n", result);
32 free(result);
33 return 0;
34}
35The C solution uses a dynamic character array res to construct the result string, simulating a stack. An auxiliary array count keeps track of the current streak of consecutive characters. When the count reaches k, the top character is removed.
This approach utilizes a two-pointer technique to modify the string in place. Here, we treat the string as a character array, using one pointer to scan the input and another to build the output string. A helper array is used to store counts of consecutive characters.
Time Complexity: O(n)
Space Complexity: O(n)
1
The C solution employs an extra integer array to keep track of the count of consecutive characters for each position j in the resultant array. Characters are removed in-place by adjusting the index j accordingly.