Sponsored
Sponsored
Use a stack data structure to efficiently remove adjacent duplicates. Traverse through the string, and for each character, check the top of the stack. If the top of the stack is equal to the current character, pop the stack. Otherwise, push the current character onto the stack. Finally, reconstruct the string from the stack.
Time Complexity: O(n), where n is the length of the string since we traverse the string once.
Space Complexity: O(n), as in the worst case, the stack may need to store all characters.
1#include <iostream>
2#include <string>
3
4std::string removeDuplicates(const std::string& s) {
5 std::string stack;
6 for (char c : s) {
7 if (!stack.empty() && stack.back() == c) {
8 stack.pop_back(); // Remove last character
9 } else {
10 stack.push_back(c); // Add current character
11 }
12 }
13 return stack;
14}
15
16int main() {
17 std::string s = "abbaca";
18 std::cout << removeDuplicates(s) << std::endl;
19 return 0;
20}We use a dynamic string as a stack, where characters are added and removed from the end of the string. If two characters are the same (adjacent duplicates), the function removes them from the stack by popping the last character.
This approach also simulates stack behavior but uses a two-pointer technique on the same string to efficiently manage space without using additional data structures. It leverages the properties of strings and index manipulation to override adjacent duplicates.
Time Complexity: O(n), with n being the string length.
Space Complexity: O(1), since it modifies the original string in place.
1
The two-pointer method directly modifies the input string array by using `i` as the effective end of the currently processed string. Whenever a duplicate is detected, we backtrack the `i` pointer, simulating a pop operation. This way, space usage is minimized as no extra stack structure is created.