LeetCode 1047: Remove All Adjacent Duplicates In String

Problem Restatement

We are given a string s.

In one step, we choose two adjacent equal letters and remove them.

We repeat this until no adjacent equal letters remain.

Return the final string.

The result is always unique regardless of the order of removals.

The official constraints state that 1 <= s.length <= 10^5 and s consists only of lowercase English letters.

Input and Output

Function shape:

def removeDuplicates(s: str) -> str:
    ...

Examples

Example 1:

s = "abbaca"

Remove "bb": "aaca". Remove "aa": "ca".

Answer:

"ca"

Example 2:

s = "azxxzy"

Remove "xx": "azzy". Remove "zz": "ay".

Answer:

"ay"

Key Insight

Use a stack.

For each character:

• If the stack is non-empty and its top equals the current character, pop the top (remove the pair).
• Otherwise, push the character.

The stack holds the current string without adjacent duplicates.

Correctness

At each step, we check if the new character forms a pair with the top of the stack. If so, removing them may expose a new pair at the top. The stack naturally handles cascading removals.

Edge Cases

• The stack should store exactly the unresolved items needed by the invariant.
• Process equal values deliberately; many monotonic-stack problems differ only in < versus <=.
• Flush or inspect the remaining stack after the scan if unresolved items still contribute to the answer.

Complexity

Common Pitfalls

• Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
• Prefer problem-specific names over one-letter variables once the logic becomes stateful.

Implementation

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

Testing

def run_tests():
    s = Solution()

    assert s.removeDuplicates("abbaca") == "ca"
    assert s.removeDuplicates("azxxzy") == "ay"
    assert s.removeDuplicates("a") == "a"
    assert s.removeDuplicates("aa") == ""
    assert s.removeDuplicates("aabb") == ""

    print("all tests passed")

run_tests()