Problem Description

Given a string s, repeatedly remove all adjacent duplicate characters in the string until no more adjacent duplicates remain. Return the final string after all such removals have been performed.

• Each time two adjacent characters in s are the same, both are removed.
• The process is repeated until no more adjacent duplicates exist.
• Only adjacent duplicates are removed, not all duplicates in the string.
• s contains only lowercase English letters.
• The problem guarantees one valid solution for every input.

Example:
Input: s = "abbaca"
Output: "ca"

Thought Process

At first glance, the problem seems to suggest checking for duplicate letters and removing them. However, the key is that only adjacent duplicates are removed, and this process must be repeated because removing one pair can create new adjacent duplicates.

A brute-force approach might involve scanning the string for adjacent duplicates, removing them, and repeating the scan until no more duplicates are found. However, this would be inefficient, especially for long strings, as each scan could be O(n) and we might do it many times.

To optimize, we can use a stack data structure. As we iterate through the string, we compare each character with the top of the stack (the last character we processed). If they match, we pop the last character (removing both duplicates). If not, we push the character onto the stack. This way, we process each character only once, and the stack naturally handles the repeated removal process.

Solution Approach

The optimized approach uses a stack to efficiently remove adjacent duplicates:

1. Initialize an empty stack (can be a list or array).
2. Iterate through each character c in the input string s:
   • If the stack is not empty and the top of the stack equals c, pop the stack (remove the duplicate pair).
   • Otherwise, push c onto the stack.
3. After processing all characters, the stack contains the result string (with all adjacent duplicates removed). Join the stack into a string and return it.

Why this works: The stack always contains the current non-duplicate sequence. When a duplicate is found, both are removed. If removing a pair creates a new adjacent duplicate, the stack allows us to check and remove it in the same pass.

Example Walkthrough

Let's walk through the sample input s = "abbaca":

1. Start with an empty stack: []
2. Read 'a': stack is ['a']
3. Read 'b': stack is ['a', 'b']
4. Read 'b': top of stack is 'b', matches current 'b', so pop. Stack is ['a']
5. Read 'a': top of stack is 'a', matches, so pop. Stack is []
6. Read 'c': stack is ['c']
7. Read 'a': stack is ['c', 'a']

Final stack: ['c', 'a']
Join to string: "ca"

Why this works: Each time we encounter a duplicate, both are removed instantly. The process is repeated naturally as the stack allows us to check for new adjacent duplicates after each removal.

Code Implementation

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

class Solution {
public:
    string removeDuplicates(string s) {
        string stack;
        for (char c : s) {
            if (!stack.empty() && stack.back() == c) {
                stack.pop_back();
            } else {
                stack.push_back(c);
            }
        }
        return stack;
    }
};
      

class Solution {
    public String removeDuplicates(String s) {
        StringBuilder stack = new StringBuilder();
        for (char c : s.toCharArray()) {
            int len = stack.length();
            if (len > 0 && stack.charAt(len - 1) == c) {
                stack.deleteCharAt(len - 1);
            } else {
                stack.append(c);
            }
        }
        return stack.toString();
    }
}
      

var removeDuplicates = function(s) {
    const stack = [];
    for (let c of s) {
        if (stack.length > 0 && stack[stack.length - 1] === c) {
            stack.pop();
        } else {
            stack.push(c);
        }
    }
    return stack.join('');
};
      

Time and Space Complexity

• Brute-force approach:
  • Time Complexity: O(n²) in the worst case, because each scan could take O(n) and could be repeated up to O(n) times.
  • Space Complexity: O(n) for the string being processed.
• Optimized (stack) approach:
  • Time Complexity: O(n), since each character is pushed and popped at most once.
  • Space Complexity: O(n), for the stack to store the result characters in the worst case (no duplicates).

The stack approach is much more efficient and suitable for large strings.

Summary

The problem of removing all adjacent duplicates in a string can be solved efficiently with a stack-based approach. By processing each character once and using the stack to manage removal and re-checking for new duplicates, we achieve a clean O(n) solution. This method is both simple and powerful, demonstrating how the right data structure can transform a repeated-process problem into a single-pass algorithm.