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.
1public class RemoveDuplicates {
2 public static String removeDuplicates(String s) {
3 StringBuilder stack = new StringBuilder();
4 for (char c : s.toCharArray()) {
5 int length = stack.length();
6 if (length > 0 && stack.charAt(length - 1) == c) {
7 stack.deleteCharAt(length - 1); // Remove last character
8 } else {
9 stack.append(c); // Add current character
10 }
11 }
12 return stack.toString();
13 }
14 public static void main(String[] args) {
15 System.out.println(removeDuplicates("abbaca"));
16 }
17}The StringBuilder class is used to manage a dynamic string stack. Characters are appended or removed based on whether they match the top of the current stack.
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.
1In this Java implementation, the function modifies the character array directly. `i` serves as the stack pointer, while `j` traverses through the character array. When duplicates are encountered, they are overwritten by the next unique character at `i-2`.