A physics simulation feeds you a stream of particles as a string of letters. Each letter names a particle species, and its case marks polarity — an uppercase letter and its lowercase twin (for example 'Q' and 'q') are matter and antimatter partners of the same species. Whenever two partner particles of the same species end up standing directly next to each other anywhere in the stream, they annihilate: both vanish instantly and the stream closes the gap, which may bring a brand-new pair of partners together and trigger another annihilation. Simulate this cascading annihilation until no two adjacent particles in the stream are partners, and report the surviving stream.
A single line containing the particle stream s, consisting only of English letters (uppercase and lowercase).
Print the final surviving stream after all possible annihilations have cascaded to completion. If every particle annihilates away, print an empty line.
Example 1
Input
abBAcC
Expected
(empty)Explanation
Scan left to right keeping a stack of survivors: push 'a', push 'b'. The next character 'B' is the antimatter partner of the 'b' on top, so both annihilate, leaving just 'a' on the stack. The next character 'A' is the partner of that 'a', so they annihilate too, leaving the stack empty. Push 'c', then 'C' annihilates with it, leaving the stack empty again. Every particle annihilated, so the output is an empty line.
Example 2
Input
xXyYz
Expected
z
Explanation
Push 'x', then 'X' annihilates with it (stack empty). Push 'y', then 'Y' annihilates with it (stack empty). Push 'z' — there is nothing after it to pair with, so it survives. The final surviving stream is "z".
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →