594. Remove All Adjacent Duplicates In String
You are given a string s of lowercase English letters.
A duplicate removal deletes one pair of equal letters that sit right next to each other. Removing a pair can create a brand-new adjacent pair out of the letters that were on either side of it, and you keep removing until no two neighboring letters are equal.
Return the string that remains once no more removals are possible. The order you remove pairs in never changes the final result, so the answer is unique — it may even be empty.
Example 1:
Input: s = "abbaca"
Output: "ca"
Explanation: Delete the pair "bb" to get "aaca". That deletion pushes the two a's together, so "aa" cancels next, leaving "ca" — no equal neighbors remain.
Example 2:
Input: s = "azxxzy"
Output: "ay"
Explanation: Removing "xx" gives "azzy", which exposes the new pair "zz". Removing it gives "ay".
Constraints:
- 1 ≤ s.length ≤ 10⁵
- s consists of lowercase English letters.
Hints:
Deleting a pair can make the letters on either side of it adjacent — a chain reaction. Restarting the scan from the beginning after every deletion is correct but quadratic. Can one pass handle the cascade?
Walk left to right keeping a stack of survivors: if the current letter equals the top of the stack, pop it (the pair cancels — and the previous survivor is now exposed for future matches); otherwise push. Whatever is on the stack at the end is the answer, already in order.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: s = "abbaca"
Expected output: "ca"