DSA problem
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. Repeatedly perform duplicate removals on s until no more can be made. Return the final string after all such duplicate removals have been completed. It is guaranteed that the answer is unique.
For example, in "abbaca" you can remove the adjacent "bb" to get "aaca", then remove the adjacent "aa" to get "ca". No more adjacent duplicates remain, so "ca" is the answer.
A naive approach would scan the string repeatedly, removing pairs in each pass until a full pass makes no changes. In the worst case (a long run of pairs that cascade after removal) this becomes O(n^2).
The stack-based approach is far cleaner. Walk the string left to right and maintain a stack of characters seen so far. For each new character, if the stack's top equals it, pop the top (those two cancel); otherwise push the character. The cancellation naturally cascades — any new top revealed by a pop is then compared with the next incoming character. At the end, the stack contains the result string from bottom to top. This is one pass, O(n) time, O(n) space.
Examples
s = "abbaca""ca"s = "azxxzy""ay"s = "aaaaaaaa"""Constraints
- 1 <= s.length <= 10^5
- s consists of lowercase English letters.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.