Problem Description

You have a string s made up of lowercase English letters. Your task is to repeatedly remove adjacent duplicate characters until no more removals are possible.

A duplicate removal works like this: find two adjacent letters that are the same and remove both of them from the string. After each removal, the remaining parts of the string come together, potentially creating new adjacent duplicates that can be removed.

For example:

• If you have "abbaca", you can remove "bb" to get "aaca", then remove "aa" to get "ca". No more adjacent duplicates exist, so "ca" is the final answer.
• If you have "azxxzy", you can remove "xx" to get "azzy", then remove "zz" to get "ay". No more adjacent duplicates exist, so "ay" is the final answer.

The process continues until there are no adjacent duplicate pairs left in the string. The problem guarantees that the final result is unique regardless of the order in which you perform the removals.

The solution uses a stack-based approach: iterate through each character in the string, and if the top of the stack matches the current character, pop the stack (removing the duplicate pair). Otherwise, push the current character onto the stack. The final stack contents represent the string after all duplicate removals.

Intuition

When we think about removing adjacent duplicates, we need to consider what happens after each removal - the characters on either side of the removed pair come together and might form a new duplicate pair. This suggests we need a way to efficiently handle these cascading removals.

Consider the string "abbaca". If we process it left to right:

• We see 'a', nothing to compare with yet
• We see 'b', different from 'a', so keep both
• We see another 'b', same as the previous one - remove both
• Now we have 'a' and need to process 'a' next
• These two 'a's are now adjacent - remove both
• Continue with 'c' and 'a'

This process naturally follows a Last-In-First-Out (LIFO) pattern. When we encounter a character, we need to check it against the most recently kept character. If they match, we remove both (the current one and the most recent kept one). If they don't match, we keep the current character as the new "most recent."

A stack is the perfect data structure for this LIFO behavior. As we traverse the string:

• If the stack is empty or the top element doesn't match the current character, we push the current character
• If the top element matches the current character, we pop the stack (removing the duplicate) and don't add the current character

This way, the stack always maintains the characters that haven't been removed yet, and adjacent duplicates are automatically eliminated as we process each character. The final stack contents give us the string after all possible removals.

Learn more about Stack patterns.

Solution Approach

The implementation uses a stack to efficiently handle the duplicate removal process. Here's how the algorithm works step by step:

1. Initialize an empty stack: stk = [] - This will store the characters that remain after removing duplicates.

2. Iterate through each character in the string: for c in s: - Process the string from left to right, one character at a time.

3. Check for duplicate pairs:

   • if stk and stk[-1] == c: - Check if the stack is not empty AND the top element (last element in the list) equals the current character
   • If true: stk.pop() - Remove the top element from the stack (this simulates removing both the current character and its duplicate)
   • If false: stk.append(c) - Add the current character to the stack (no duplicate found)

4. Build the final result: return ''.join(stk) - Convert the stack (list of characters) back into a string.

Example walkthrough with "abbaca":

• Process 'a': Stack is empty, push 'a' → Stack: ['a']
• Process 'b': Top is 'a' ≠ 'b', push 'b' → Stack: ['a', 'b']
• Process 'b': Top is 'b' = 'b', pop stack → Stack: ['a']
• Process 'a': Top is 'a' = 'a', pop stack → Stack: []
• Process 'c': Stack is empty, push 'c' → Stack: ['c']
• Process 'a': Top is 'c' ≠ 'a', push 'a' → Stack: ['c', 'a']
• Result: "ca"

The time complexity is O(n) where n is the length of the string, as we process each character once. The space complexity is also O(n) in the worst case when no duplicates are removed.

Example Walkthrough

Let's walk through the solution with the string "azxxzy" to see how the stack-based approach removes all adjacent duplicates.

Initial state:

• Input string: "azxxzy"
• Stack: [] (empty)

Step-by-step process:

1. Process 'a':

   • Stack is empty, so push 'a'
   • Stack: ['a']

2. Process 'z':

   • Top of stack is 'a' ≠ 'z', so push 'z'
   • Stack: ['a', 'z']

3. Process first 'x':

   • Top of stack is 'z' ≠ 'x', so push 'x'
   • Stack: ['a', 'z', 'x']

4. Process second 'x':

   • Top of stack is 'x' = 'x', so pop the stack (removing the duplicate pair)
   • Stack: ['a', 'z']

5. Process 'z':

   • Top of stack is 'z' = 'z', so pop the stack (removing this duplicate pair)
   • Stack: ['a']

6. Process 'y':

   • Top of stack is 'a' ≠ 'y', so push 'y'
   • Stack: ['a', 'y']

Final result: Join the stack elements to get "ay"

Notice how when we removed the 'xx' pair in step 4, it brought the two 'z' characters together, which we then removed in step 5. This cascading effect is exactly what the stack handles automatically - we don't need to restart or look back, the stack maintains the correct state throughout the process.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the input string s. The algorithm iterates through each character in the string exactly once. Each operation inside the loop (checking the top of the stack, pushing, and popping) takes O(1) time. The final join operation also takes O(n) time to concatenate all remaining characters in the stack. Therefore, the overall time complexity is O(n) + O(n) = O(n).

Space Complexity: O(n), where n is the length of the input string s. In the worst case scenario, when no adjacent duplicates exist in the string (e.g., "abcdef"), all characters will be pushed onto the stack, requiring O(n) space. The output string created by join also requires O(n) space in the worst case, but since we typically only count auxiliary space and the output is required, the space complexity remains O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Attempting String Concatenation Instead of Using a Stack

A common mistake is trying to build the result string directly through concatenation, which leads to inefficient code and complexity in handling removals:

Incorrect Approach:

def removeDuplicates(self, s: str) -> str:
    result = ""
    for char in s:
        if result and result[-1] == char:
            result = result[:-1]  # String slicing creates a new string
        else:
            result += char  # String concatenation creates a new string
    return result

Why it's problematic:

• Strings are immutable in Python, so each concatenation or slicing operation creates a new string object
• This leads to O(n²) time complexity instead of O(n)
• Memory usage becomes inefficient due to multiple string copies

Solution: Use a list (stack) to collect characters and join them at the end, as shown in the correct implementation.

2. Forgetting to Check if Stack is Empty

Incorrect Code:

def removeDuplicates(self, s: str) -> str:
    stack = []
    for char in s:
        if stack[-1] == char:  # ERROR: Will crash when stack is empty
            stack.pop()
        else:
            stack.append(char)
    return ''.join(stack)

Why it fails:

• Accessing stack[-1] when the stack is empty raises an IndexError
• This happens at the start of iteration or after removing pairs that empty the stack

Solution: Always check if stack and stack[-1] == char: to ensure the stack has elements before accessing the top.

3. Misunderstanding the Problem - Removing Only First Occurrence

Some might incorrectly think they should remove duplicates only once without considering chain reactions:

Incorrect Logic:

def removeDuplicates(self, s: str) -> str:
    i = 0
    while i < len(s) - 1:
        if s[i] == s[i + 1]:
            s = s[:i] + s[i+2:]  # Remove the pair
            # Incorrect: just continue without reconsidering position
            continue
        i += 1
    return s

Why it's wrong:

• After removing a pair, new adjacent duplicates might form
• The algorithm must reconsider the position after each removal
• Using string slicing for in-place modification is inefficient

Solution: The stack approach naturally handles chain reactions - when we pop an element, the next comparison automatically happens with the newly exposed top element.