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.
1def removeDuplicates(s: str, k: int) -> str:
2 stack = []
3 for char in s:
4 if stack and stack[-1][0] == char:
5 stack[-1][1] += 1
6 else:
7 stack.append([char, 1])
8 if stack[-1][1] == k:
9 stack.pop()
10 return ''.join(char * cnt for char, cnt in stack)
11
12# Example usage
13s = "deeedbbcccbdaa"
14k = 3
15print(removeDuplicates(s, k)) # Output: "aa"
16This Python solution uses a list to simulate a stack, where each element is a tuple containing the character and its current count. If the count reaches k, the character is popped from the stack.
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#include <string>
std::string removeDuplicates(std::string s, int k) {
int j = 0;
std::vector<int> count(s.size());
for (int i = 0; i < s.size(); ++i) {
s[j] = s[i];
count[j] = (j > 0 && s[j] == s[j - 1]) ? count[j - 1] + 1 : 1;
if (count[j] == k) {
j -= k;
}
++j;
}
return s.substr(0, j);
}
int main() {
std::string s = "deeedbbcccbdaa";
int k = 3;
std::cout << removeDuplicates(s, k) << std::endl;
return 0;
}
The C++ solution modifies the input string in-place using two pointers. An auxiliary vector carries the count of each character's occurrence and helps decide when the substring should be removed.