LeetCode 1047 - Remove All Adjacent Duplicates In String

LeetCode Problem 1047

Difficulty: 🟢 Easy
Topics: String, Stack

Solution

Problem Understanding

The problem gives us a string s containing only lowercase English letters. We repeatedly look for two adjacent characters that are equal, remove both of them, and continue this process until no such adjacent duplicate pair exists.

The important detail is that removals can create new adjacent duplicates that were not adjacent before. For example, in the string "abbaca", removing "bb" produces "aaca", which then contains "aa" as a new adjacent duplicate pair. After removing "aa", the final result becomes "ca".

The task is to return the final string after all possible duplicate removals have been completed. The problem guarantees that the final answer is unique, regardless of the order in which removals are performed.

The input size can be as large as 10^5 characters. This constraint immediately tells us that inefficient repeated string reconstruction approaches may become too slow. Since strings are immutable in Python and expensive to repeatedly modify in many languages, we need an approach that processes the string efficiently in a single pass if possible.

Several edge cases are important to recognize early:

• A string with no adjacent duplicates should remain unchanged.
• A string where every character eventually disappears should return an empty string.
• Removing one pair may create another removable pair.
• Long runs of repeated characters, such as "aaaa", require repeated collapsing behavior.
• The smallest valid input has length 1, which can never contain duplicates.

Approaches

Brute Force Approach

A straightforward solution is to repeatedly scan the string looking for adjacent duplicate characters. Whenever we find such a pair, we remove it and restart the scan from the beginning.

For example:

• "abbaca"
• Remove "bb" → "aaca"
• Remove "aa" → "ca"

This approach works because eventually all removable pairs are eliminated. However, each removal creates a brand new string, and we may repeatedly rescan large portions of the input.

In the worst case, each removal operation costs O(n) time because strings must be rebuilt, and we may perform up to O(n) removals. This leads to quadratic complexity.

With n up to 100000, an O(n^2) solution is too slow.

Optimal Approach, Stack Simulation

The key observation is that the problem behaves exactly like stack cancellation.

As we process characters from left to right:

• If the current character matches the top of the stack, we remove the top element instead of adding the current character.
• Otherwise, we push the current character onto the stack.

This works because adjacent duplicates always interact locally with the most recently retained character.

For example:

• Stack: ['a']
• Read 'b' → push
• Stack: ['a', 'b']
• Read 'b' → matches top, pop
• Stack: ['a']

The stack always represents the current valid string after processing the characters seen so far.

Because every character is pushed and popped at most once, the algorithm runs in linear time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Repeatedly scans and rebuilds the string
Optimal	O(n)	O(n)	Uses a stack to process each character once

Algorithm Walkthrough

Optimal Stack Algorithm

1. Initialize an empty stack.

The stack will store the characters that remain after processing duplicate removals so far. 2. Iterate through each character in the input string.

We process the string from left to right because adjacent relationships only depend on nearby characters. 3. For each character, check the top of the stack.

If the stack is not empty and the top character equals the current character, then we have found an adjacent duplicate pair. 4. Remove the duplicate pair.

Instead of adding the current character, pop the top character from the stack. This simulates removing both adjacent duplicate characters. 5. Otherwise, push the current character onto the stack.

If the current character does not match the top of the stack, it cannot form a removable adjacent pair at this moment. 6. Continue until all characters are processed.

The stack now contains the final valid string after all removals. 7. Convert the stack back into a string.

Join all characters in the stack and return the result.

Why it works

The stack always stores the fully processed result for the prefix of the string examined so far. Whenever a new character matches the top of the stack, the two characters would become adjacent duplicates in the final string, so removing them immediately is correct. Since every cancellation is handled exactly when it becomes possible, the stack state always matches the correct intermediate string. By the end of the traversal, no adjacent duplicates remain.

Python Solution

class Solution:
    def removeDuplicates(self, s: str) -> str:
        stack: list[str] = []

        for char in s:
            if stack and stack[-1] == char:
                stack.pop()
            else:
                stack.append(char)

        return "".join(stack)

The implementation uses a list as a stack because Python lists support efficient append and pop operations at the end.

The variable stack stores the characters that remain after processing duplicate removals so far.

During iteration:

• stack[-1] accesses the top element.
• If the current character matches the top, we remove the top using pop().
• Otherwise, we add the character using append().

At the end, the stack contains the final remaining characters in order, so "".join(stack) converts it back into the required string.

This implementation directly follows the algorithm described earlier and guarantees linear time complexity.

Go Solution

func removeDuplicates(s string) string {
    stack := make([]byte, 0)

    for i := 0; i < len(s); i++ {
        current := s[i]

        if len(stack) > 0 && stack[len(stack)-1] == current {
            stack = stack[:len(stack)-1]
        } else {
            stack = append(stack, current)
        }
    }

    return string(stack)
}

The Go implementation uses a byte slice as the stack because the input only contains lowercase English letters.

Unlike Python lists, Go slices require explicit slicing to remove the last element:

stack = stack[:len(stack)-1]

Appending uses the built in append function.

The final byte slice is converted back into a string using:

string(stack)

Since the input only contains ASCII lowercase letters, using bytes is both correct and efficient.

Worked Examples

Example 1

Input:

s = "abbaca"

Step	Current Character	Stack Before	Action	Stack After
1	a	[]	push	[a]
2	b	[a]	push	[a, b]
3	b	[a, b]	pop matching b	[a]
4	a	[a]	pop matching a	[]
5	c	[]	push	[c]
6	a	[c]	push	[c, a]

Final result:

"ca"

Example 2

Input:

s = "azxxzy"

Step	Current Character	Stack Before	Action	Stack After
1	a	[]	push	[a]
2	z	[a]	push	[a, z]
3	x	[a, z]	push	[a, z, x]
4	x	[a, z, x]	pop matching x	[a, z]
5	z	[a, z]	pop matching z	[a]
6	y	[a]	push	[a, y]

Final result:

"ay"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is pushed and popped at most once
Space	O(n)	The stack may store all characters in the worst case

The algorithm processes each character exactly one time. Every character can enter the stack once and leave the stack once, so the total amount of stack work is linear.

The worst case for space occurs when the string contains no adjacent duplicates, meaning the stack grows to size n.

Test Cases

solution = Solution()

assert solution.removeDuplicates("abbaca") == "ca"  # Provided example
assert solution.removeDuplicates("azxxzy") == "ay"  # Chain reactions after removals

assert solution.removeDuplicates("a") == "a"  # Single character
assert solution.removeDuplicates("aa") == ""  # Entire string removed
assert solution.removeDuplicates("aaa") == "a"  # Odd count leaves one character
assert solution.removeDuplicates("aaaa") == ""  # Even count fully cancels

assert solution.removeDuplicates("abc") == "abc"  # No duplicates
assert solution.removeDuplicates("aabccb") == ""  # Entire string collapses
assert solution.removeDuplicates("mississippi") == "m"  # Multiple cascading removals

assert solution.removeDuplicates("abba") == ""  # Nested cancellation
assert solution.removeDuplicates("abccba") == ""  # Full chain reaction
assert solution.removeDuplicates("abcdefggfedcba") == ""  # Large symmetric cancellation

assert solution.removeDuplicates("ababab") == "ababab"  # No adjacent duplicates
assert solution.removeDuplicates("zzzyyy") == "zy"  # Partial cancellation

Test	Why
"abbaca"	Validates the provided example
"azxxzy"	Verifies cascading removals
"a"	Smallest valid input
"aa"	Complete removal case
"aaa"	Odd repetition count
"aaaa"	Even repetition count
"abc"	No duplicates exist
"aabccb"	Entire string disappears
"mississippi"	Multiple removal waves
"abba"	Nested duplicate interactions
"abccba"	Chain reactions across the string
"abcdefggfedcba"	Long cascading collapse
"ababab"	Alternating pattern without removals
"zzzyyy"	Partial reduction with leftovers

Edge Cases

Single Character Input

A string of length one can never contain adjacent duplicates. A naive implementation that assumes pairs exist may accidentally access invalid indices or perform unnecessary operations.

The stack based solution handles this naturally. The single character is pushed once and returned unchanged.

Entire String Disappears

Inputs such as "aa" or "abba" eventually remove every character. Some implementations incorrectly return None or fail when converting an empty structure back into a string.

This implementation correctly returns an empty string because joining an empty stack produces "".

Cascading Duplicate Creation

The most important edge case is when removing one pair creates another removable pair. For example:

"abccba"

Removing "cc" creates "abba", which then creates "aa" after removing "bb".

A naive single pass approach without backtracking would fail here. The stack solves this automatically because after a pop operation, the new top element immediately becomes available for comparison with future characters.