Remove All Adjacent Duplicates in String

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 <= 105
• s consists of lowercase English letters.

Approach: Stack (Optimal Solution)

Algorithm

1. Use a stack to store the result characters
2. Iterate through each character
3. If the stack’s top equals the current character, pop it (removing the adjacent pair)
4. Otherwise, push the current character
5. After processing all characters, the stack contains the final result

Key Insight

When a character matches the top of the stack, both are removed. This may expose a new character on top that now matches a following character, and the stack naturally continues the process. This mirrors the repeated duplicate removal without extra passes.

Time & Space Complexity

• Time Complexity: O(n) - single pass through the string
• Space Complexity: O(n) - stack stores up to n characters

Java Implementation

import java.util.Stack;

public class RemoveAllAdjacentDuplicatesInString {

    /**
     * Remove all adjacent duplicate letters repeatedly until no more removals are possible.
     * @param s Input string
     * @return Final string after all duplicate removals
     */
    public static String removeDuplicates(String s) {
        Stack<Character> stack = new Stack<>();

        for (char c : s.toCharArray()) {
            // If the current character matches the top, remove the pair
            if (!stack.isEmpty() && stack.peek() == c) {
                stack.pop();
            } else {
                stack.push(c);
            }
        }

        // Build the result from the stack
        StringBuilder result = new StringBuilder();
        for (char c : stack) {
            result.append(c);
        }

        return result.toString();
    }

    // Test method
    public static void main(String[] args) {
        // Test case 1
        System.out.println("Input: s = \"abbaca\"");
        System.out.println("Output: \"" + removeDuplicates("abbaca") + "\""); // Expected: "ca"

        // Test case 2
        System.out.println("Input: s = \"azxxzy\"");
        System.out.println("Output: \"" + removeDuplicates("azxxzy") + "\""); // Expected: "ay"
    }
}

Example Walkthrough

For s = "abbaca":

1. c=‘a’: stack empty, push ‘a’ → stack=[a]
2. c=‘b’: ‘b’ != ‘a’, push ‘b’ → stack=[a,b]
3. c=‘b’: ‘b’ == top ‘b’, pop → stack=[a]
4. c=‘a’: ‘a’ == top ‘a’, pop → stack=[]
5. c=‘c’: stack empty, push ‘c’ → stack=[c]
6. c=‘a’: ‘a’ != ‘c’, push ‘a’ → stack=[c,a]

Result = “ca”.

For s = "azxxzy":

1. c=‘a’: push → [a]
2. c=‘z’: push → [a,z]
3. c=‘x’: push → [a,z,x]
4. c=‘x’: pop → [a,z]
5. c=‘z’: pop → [a]
6. c=‘y’: push → [a,y]

Result = “ay”.

Alternative Approach: StringBuilder as Stack

public static String removeDuplicatesWithBuilder(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();
}

This variant uses a StringBuilder directly as the stack, avoiding an extra conversion step.

Key Insights

1. Single Pass: One traversal handles all consecutive duplicate removals
2. Adjacent Pairs: Only removes exactly two adjacent equal characters at a time
3. Chained Removals: Popping can expose new top characters, enabling chained removals like “abbaca” → “aaca” → “ca”
4. Unique Answer: The final result is guaranteed unique regardless of removal order

The stack-based approach is the optimal solution, providing linear time complexity.