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.
1function removeDuplicates(s, k) {
2 const stack = [];
3 for (const char of s) {
4 if (stack.length && stack[stack.length - 1][0] === char) {
5 stack[stack.length - 1][1] += 1;
6 } else {
7 stack.push([char, 1]);
8 }
9 if (stack[stack.length - 1][1] === k) {
10 stack.pop();
11 }
12 }
13 return stack.map(pair => pair[0].repeat(pair[1])).join('');
14}
15
16// Example usage:
17console.log(removeDuplicates("deeedbbcccbdaa", 3)); // "aa"
18This JavaScript solution employs an array to simulate a stack, where each element is a pair comprising a character and its streak count. The function efficiently concatenates the remaining characters to form the result string.
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)
1using System.Text;
public class Solution {
public string RemoveDuplicates(string s, int k) {
char[] stack = s.ToCharArray();
int[] count = new int[s.Length];
int j = 0;
for (int i = 0; i < s.Length; i++, j++) {
stack[j] = stack[i];
count[j] = (j > 0 && stack[j] == stack[j - 1]) ? count[j - 1] + 1 : 1;
if (count[j] == k) {
j -= k;
}
}
return new string(stack, 0, j);
}
public static void Main(string[] args) {
var solution = new Solution();
Console.WriteLine(solution.RemoveDuplicates("deeedbbcccbdaa", 3));
}
}
This C# solution leverages array modifications and counts to manage and remove sequences of duplicates in-place, allowing us to handle the string without extra space for additional structures.