1047.md

1047. Remove All Adjacent Duplicates In String

Level:

Topic:

Similar Problem:

• 1249. Minimum Remove to Make Valid Parentheses

Question

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.

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".

Intuition

• Use stack to maintain unique characters to the respect of the current left

1. only add to stack if there is no duplicate in the stack or the stack is empty
2. if the top of the stack is a duplicate remove it and not add the current
3. construct the final answer by the reverse order of the stack

Code

Time: O(n)
Space: O(n)

public String removeDuplicates(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (stack.isEmpty() || stack.peekLast() != c)
            stack.addLast(c);
        else
            stack.removeLast();
    }

    StringBuilder ans = new StringBuilder();
    while (!stack.isEmpty())
        ans.append(stack.removeFirst());

    return ans.toString();
}