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.
1using System;
2using System.Collections.Generic;
3using System.Text;
4
5public class Solution {
6 public string RemoveDuplicates(string s, int k) {
7 Stack<int> counts = new Stack<int>();
8 StringBuilder sb = new StringBuilder();
9
10 foreach (char c in s) {
11 if (sb.Length > 0 && sb[sb.Length - 1] == c) {
12 int newCount = counts.Pop() + 1;
13 if (newCount == k) {
14 sb.Length -= k - 1;
15 } else {
16 counts.Push(newCount);
17 }
18 } else {
19 sb.Append(c);
20 counts.Push(1);
21 }
22 }
23 return sb.ToString();
24 }
25
26 public static void Main(string[] args) {
27 var solution = new Solution();
28 Console.WriteLine(solution.RemoveDuplicates("deeedbbcccbdaa", 3)); // Output: aa
29 }
30}
31This C# solution employs a stack to keep track of the counts of characters while using a StringBuilder to efficiently build the output string. When a k streak is detected, the output string is reduced accordingly.
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
This JavaScript solution adapts the in-place approach using arrays for string modification. Arrays provide flexibility to adjust character sequences based on found duplicate counts.