Collapse Adjacent Pairs
Problem
Given a piece of text, repeatedly delete any two neighbouring characters that are identical. Deleting a pair pulls the surrounding characters together, which may create a new neighbouring pair to delete. Keep going until no such pair is left and return what remains.
Examples
Input: text = "abbaca"
Output: "ca"
Why: removing bb leaves aaca, and removing aa leaves caInput: text = "azxxzy"
Output: "ay"
Why: deleting xx creates zz, which then deletes tooInput: text = "aa"
Output: ""
Why: edge case, everything cancels and nothing is leftHints
0 / 3
Rescanning the whole text after every deletion is correct but slow. Notice that a deletion can only ever affect the characters immediately around the gap.
Build the result left to right and keep looking at its last character. A structure whose only cheap operations are add-to-the-end and remove-from-the-end fits this exactly.
Push characters onto a stack one at a time. Before pushing, compare the incoming character with the one on top: if they match, pop instead of pushing, which performs the cancellation and immediately exposes the next candidate underneath. Join the leftover stack at the end.
Solution
A stack holds the part of the answer built so far, and its top is always the character a newcomer would sit next to. A match therefore cancels by popping instead of pushing, which also exposes the character underneath as the new neighbour, so chains of cancellations happen automatically without rescanning. Each character is pushed and popped at most once. Time is O(n) and space is O(n) for the stack.
def collapse_pairs(text):
stack = []
for ch in text:
if stack and stack[-1] == ch:
stack.pop() # the pair annihilates, exposing the one below
else:
stack.append(ch)
return "".join(stack)
print(collapse_pairs("abbaca")) # -> ca
print(collapse_pairs("azxxzy")) # -> ay
print(collapse_pairs("aa")) # ->Stuck on the idea rather than the code? Valid Parentheses covers it.