Skip to interview prep
Apexed

329. Recursively remove adjacent duplicate characters, e.g. "abccba" → "" and "azxxzy" → "ay".

MediumString algorithms

Technical
Show model answer

Repeatedly scanning and deleting pairs until nothing changes is O(n²) in the worst case. A stack does it in one pass: for each character, if it equals the top of the stack, pop (the pair cancels, and this may expose a new equal neighbour); otherwise push. The stack contents at the end are the answer. O(n) time and O(n) space, or O(1) extra if you use the string’s own prefix as the stack with a write index.

If the rule is to delete entire runs of two or more equal characters (not just pairs), store (character, count) on the stack and pop a run once the next character differs; clarify which variant is wanted.

Recursively remove adjacent duplicate characters, e.g. "abccba" → "" and "azxxzy" → "ay". — Data structures & algorithms interview question — Apexed