Remove All Adjacent Duplicates In String

Difficulty: Easy | Acceptance: 73.20% | Paid: No Topics: String, Stack

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 is guaranteed the answer is unique.

• Examples
• Constraints
• Approach 1: Simulation
• Approach 2: Stack
• Approach 3: Two Pointers

Examples

Example 1:

Input: s = "abbaca"
Output: "ca"
Explanation: 
For example, in "abbaca" we could remove "bb" so the string becomes "aaca", 
then remove "aa" to get "ca". 

Example 2:

Input: s = "azxxzy"
Output: "ay"
Explanation: 
Remove "xx" to get "azzy", then remove "zz" to get "ay".

Constraints

1 <= s.length <= 10⁵
s consists of lowercase English letters.

Approach 1: Simulation

Intuition Repeatedly scan the string from left to right. Whenever two adjacent characters are the same, remove them and restart the scan or continue checking the new adjacent characters formed by the removal.

Steps

• Iterate through the string while changes are being made.
• In each pass, look for the first pair of adjacent duplicates.
• If found, remove them and restart the process or adjust the index to check the previous character.
• If no duplicates are found in a full pass, return the string.

class Solution:
    def removeDuplicates(self, s: str) -> str:
        changed = True
        while changed:
            changed = False
            i = 0
            while i < len(s) - 1:
                if s[i] == s[i+1]:
                    s = s[:i] + s[i+2:]
                    changed = True
                    # Do not increment i, check new pair at i
                else:
                    i += 1
        return s

Complexity

• Time: O(n²) - In the worst case (e.g., “abbbba”), we might scan the string multiple times.
• Space: O(n) - To store the modified string.
• Notes: This approach is intuitive but inefficient for large inputs due to repeated string reconstruction.

Approach 2: Stack

Intuition Use a stack to keep track of characters. Iterate through the string, and if the current character matches the top of the stack, pop the stack (removing the pair). Otherwise, push the current character onto the stack.

Steps

• Initialize an empty stack.
• Iterate through each character in the string.
• If the stack is not empty and the top element equals the current character, pop the stack.
• Otherwise, push the current character onto the stack.
• After processing all characters, construct the result string from the stack.

class Solution:
    def removeDuplicates(self, s: str) -> str:
        stack = []
        for char in s:
            if stack and stack[-1] == char:
                stack.pop()
            else:
                stack.append(char)
        return ''.join(stack)

Complexity

• Time: O(n) - Each character is pushed and popped at most once.
• Space: O(n) - In the worst case, the stack stores all characters (e.g., “abc”).
• Notes: This is the standard optimal approach for this problem.

Approach 3: Two Pointers

Intuition Treat the string itself as a stack. Use a pointer i to represent the top of the stack. Iterate through the string with pointer j. If the character at i-1 matches s[j], decrement i (simulating a pop). Otherwise, copy s[j] to s[i] and increment i.

Steps

• Initialize i = 0.
• Iterate j from 0 to n-1.
• If i > 0 and s[i-1] == s[j], decrement i.
• Otherwise, set s[i] = s[j] and increment i.
• Return the substring of s from index 0 to i.

class Solution:
    def removeDuplicates(self, s: str) -> str:
        res = list(s)
        i = 0
        for char in s:
            if i > 0 and res[i-1] == char:
                i -= 1
            else:
                res[i] = char
                i += 1
        return ''.join(res[:i])

Complexity

• Time: O(n) - Single pass through the string.
• Space: O(n) - To store the character array (strings are immutable in many languages). In C++, this modifies in-place with O(1) auxiliary space.
• Notes: This is an optimized version of the stack approach that avoids using extra data structures where possible.