Remove All Adjacent Duplicates In String
EasyPrompt
You are given a string s consisting of lowercase English letters. A duplicate removal consists of choosing two adjacent and equal letters and removing them.
We repeatedly make duplicate removals on s until we no longer can.
Return the final string after all such duplicate removals have been made. It can be proven that the answer is unique.
Example 1:
Input: s = "abbaca"
Output: "ca"
Explanation:
For example, in "abbaca" we could remove "bb" since the letters are adjacent and equal, and this is the only possible move. The result of this move is that the string is "aaca", of which only "aa" is possible, so the final string is "ca".Example 2:
Input: s = "azxxzy"
Output: "ay"
Constraints:
1 <= s.length <= 105sconsists of lowercase English letters.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly simulates the process described in the problem. It repeatedly scans the string, finds the first pair of adjacent duplicates, removes them, and then starts the scan over from the beginning of the new, shorter string. This continues until a full pass over the string reveals no adjacent duplicates.
Algorithm
- Start with the input string
s. - Enter a loop that continues as long as modifications are being made to the string.
- In each iteration of the loop, find the index
iof the first occurrence wheres[i] == s[i+1]. - If such a pair is found, create a new string by removing the characters at indices
iandi+1. Updatesto this new string and restart the scan from the beginning. - If a full scan of the string is completed and no adjacent duplicates are found, exit the loop.
- The final string
sis the result.
Walkthrough
This method uses a loop that continues as long as it can find and remove a pair of adjacent, identical characters. Inside the loop, it iterates through the string to find the first such pair. Upon finding one, it removes the pair, effectively shortening the string, and then breaks the inner loop to restart the scan from the beginning of the modified string. This process is guaranteed to terminate because the string's length decreases with each successful removal. While simple to conceptualize, the repeated creation of new string objects (or manipulation of a StringBuilder from the start) makes it very slow.
class Solution { public String removeDuplicates(String s) { StringBuilder sb = new StringBuilder(s); boolean found = true; while (found) { found = false; for (int i = 0; i < sb.length() - 1; i++) { if (sb.charAt(i) == sb.charAt(i + 1)) { sb.delete(i, i + 2); found = true; break; // Restart scan from the beginning } } } return sb.toString(); }}Complexity
Time
O(N^2), where N is the length of the string. In the worst-case scenario (e.g., 'abccba'), each removal operation can take O(N) time due to scanning and string/StringBuilder modification. Since there can be up to N/2 removal operations, the total time complexity is quadratic.
Space
O(N). In Java, a `StringBuilder` is used to make the string mutable, which requires O(N) space. If using immutable strings, each modification would create a new string, also leading to O(N) space usage for the intermediate strings.
Trade-offs
Pros
The logic is straightforward and directly follows the problem statement.
Cons
Extremely inefficient due to repeated scanning and string manipulations.
Likely to fail on larger test cases due to exceeding the time limit.
A more efficient approach utilizes a stack. The Last-In, First-Out (LIFO) nature of a stack is perfect for this problem. We can iterate through the string, and for each character, we compare it with the character at the top of the stack. If they match, it means we've found an adjacent duplicate pair (one from the past, one current), so we pop the stack. Otherwise, we push the current character onto the stack.
Algorithm
- Initialize an empty stack. A
Dequeimplementation likeArrayDequeis a good choice in Java. - Iterate through each character
cof the input strings. - If the stack is not empty and the character at the top of the stack (
stack.peek()) is the same as the current characterc, pop the character from the stack. - Otherwise, push the current character
conto the stack. - After iterating through the entire string, the characters in the stack, when read from bottom to top, form the result string.
- Build the final string from the characters remaining in the stack and return it.
Walkthrough
By processing the string one character at a time, we can decide whether to keep the character or not. A stack is the ideal data structure for this. When we encounter a new character, we look at the top of the stack. If the stack is empty or the top character is different, the new character cannot form a duplicate pair with the preceding character in the result, so we push it onto the stack. If the top character is the same, we have found a pair to remove, which is accomplished by simply popping the stack and not pushing the new character. After one pass, the stack contains the characters of the final string, but in reverse order of construction. We can then build the result string by reading the stack's contents from bottom to top.
import java.util.Deque;import java.util.ArrayDeque;import java.util.Iterator; class Solution { public String removeDuplicates(String s) { Deque<Character> stack = new ArrayDeque<>(); for (char c : s.toCharArray()) { if (!stack.isEmpty() && stack.peek() == c) { stack.pop(); } else { stack.push(c); } } StringBuilder result = new StringBuilder(); // Use a descending iterator to read from bottom to top of the stack Iterator<Character> iterator = stack.descendingIterator(); while (iterator.hasNext()) { result.append(iterator.next()); } return result.toString(); }}Complexity
Time
O(N), where N is the length of the string. We perform a single pass through the input string. Each character is pushed onto the stack at most once and popped at most once. Stack operations (push, pop, peek) take amortized O(1) time.
Space
O(N). In the worst-case scenario, where the string has no adjacent duplicates (e.g., 'abcdef'), the stack will grow to size N, storing all characters of the string.
Trade-offs
Pros
Optimal time complexity with a single pass.
The logic is clean and effectively solves the problem.
Cons
Requires O(N) auxiliary space for the stack.
This approach is a highly optimized version of the stack-based solution and is often the most idiomatic way to solve this in Java. Instead of using a formal Stack object, we use a StringBuilder which acts as a character stack. The end of the StringBuilder represents the top of the stack. This avoids the overhead of the Stack class and boxing/unboxing characters.
Algorithm
- Initialize an empty
StringBuilderwhich will hold the result. - Iterate through each character
cof the input strings. - Let
lenbe the current length of theStringBuilder. - If the
StringBuilderis not empty (len > 0) and its last character (sb.charAt(len - 1)) is the same as the current characterc, then we have found an adjacent duplicate. Remove the last character from theStringBuilderusingsb.deleteCharAt(len - 1). - Otherwise, append the current character
cto theStringBuilder. - After the loop finishes, convert the
StringBuilderto a string and return it.
Walkthrough
This method is conceptually identical to the stack approach but uses a StringBuilder for a more direct and often faster implementation in Java. The StringBuilder acts as our result string that we build progressively. As we iterate through the input string, we look at the last character added to our StringBuilder. If it matches the current character from the input, we remove that last character. If it doesn't match (or if the StringBuilder is empty), we append the current character. This perfectly mimics the push/pop logic of a stack using append and deleteCharAt.
This is also equivalent to a two-pointer approach. One pointer (i) iterates through the input string, and another pointer (sb.length()) tracks the end of the valid, processed result.
class Solution { public String removeDuplicates(String s) { StringBuilder sb = new StringBuilder(); for (char c : s.toCharArray()) { int len = sb.length(); if (len > 0 && sb.charAt(len - 1) == c) { sb.deleteCharAt(len - 1); } else { sb.append(c); } } return sb.toString(); }}Complexity
Time
O(N), where N is the length of the string. We iterate through the string once. `StringBuilder` operations like `append` and `deleteCharAt` at the end take amortized O(1) time.
Space
O(N). The `StringBuilder` can grow up to the size of the input string N in the worst case (no duplicates).
Trade-offs
Pros
Optimal O(N) time complexity.
Generally faster in practice than using the
Stackclass in Java due to less overhead.Code is concise and clear.
Cons
Still requires O(N) auxiliary space, which is unavoidable for this problem in Java since strings are immutable.
Solutions
Solution
class Solution {public String removeDuplicates(String s) { StringBuilder sb = new StringBuilder(); for (char c : s.toCharArray()) { if (sb.length() > 0 && sb.charAt(sb.length() - 1) == c) { sb.deleteCharAt(sb.length() - 1); } else { sb.append(c); } } return sb.toString(); }}/** * @param {string} s * @return {string} */ var removeDuplicates = function ( s ) { const stk = []; for ( const c of s ) { if ( stk . length && stk [ stk . length - 1 ] == c ) { stk . pop (); } else { stk . push ( c ); } } return stk . join ( '' ); };class Solution { public: string removeDuplicates ( string s ) { string stk ; for ( char c : s ) { if ( ! stk . empty () && stk [ stk . size () - 1 ] == c ) { stk . pop_back (); } else { stk += c ; } } return stk ; } };class Solution: def removeDuplicates(self, s: str) -> str: stk = [] for c in s: if stk and stk[- 1] == c: stk . pop() else: stk . append(c) return '' . join(stk)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.