Cancel out neighbouring pairs

Repeatedly remove any two identical letters standing next to each other, until no such pair is left. Return what remains.

Removing a pair can create a new pair, and that one goes too.

Worked example#

For abbaca:

• abbaca has bb next to each other. Remove it, leaving aaca.
• aaca now has aa, which only became neighbours after the bb went. Remove it, leaving ca.
• ca has no pair, so that is the answer.

Doing it in one pass#

Scanning the whole string again after every removal is slow, and the repeated removals are the reason. A stack avoids all of it.

Walk the letters once, keeping a stack of what has survived so far. For each letter, compare it with the top of the stack. Equal means they cancel, so pop instead of pushing. Otherwise push it.

The stack holds ca, which is the answer. The cascade is handled for free: after a pop, the next comparison is against whatever was underneath, which is exactly the new neighbour.

Constraints#

• 1 <= length <= 100000
• Lowercase letters only
• The result may be empty, in which case print nothing