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 <stdio.h>
2#include <string.h>
3
4char* removeDuplicates(char* s) {
5 int len = strlen(s);
6 char* stack = (char*)malloc(len + 1);
7 int top = -1;
8
9 for (int i = 0; i < len; i++) {
10 if (top >= 0 && stack[top] == s[i]) {
11 top--; // Pop the stack
12 } else {
13 stack[++top] = s[i]; // Push to the stack
14 }
15 }
16
17 stack[top + 1] = '\0';
18 return stack;
19}
20
21int main() {
22 char s[] = "abbaca";
23 printf("%s\n", removeDuplicates(s));
24 return 0;
25}The solution iteratively checks each character of the string. If the character matches the top of the stack, it removes it (indicating an adjacent duplicate removal). Otherwise, it pushes the character onto the stack. This simulates the removal of adjacent duplicates effectively.
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
class RemoveDuplicatesTwoPointers {
public static string RemoveDuplicates(string s) {
char[] arr = s.ToCharArray();
int i = 0;
for (int j = 0; j < arr.Length; j++, i++) {
arr[i] = arr[j];
if (i > 0 && arr[i] == arr[i - 1]) {
i -= 2;
}
}
return new String(arr, 0, i);
}
static void Main() {
Console.WriteLine(RemoveDuplicates("abbaca"));
}
}The C# solution emphasizes a character array technique for in-place replacement and reduction of duplicates. Two pointers `i` and `j` manage the configuration by selectively keeping or overwriting entries to resolve duplicates.