Adjacent-Pair Elimination

Reported in interviews at Hudson River Trading

Problem statement

You are given a string s consisting only of the characters A, B, C, and D. You may repeatedly perform the following move: find any two adjacent characters that form one of the pairs "AB", "BA", "CD", or "DC", and delete both of them (the characters on either side then become adjacent). Repeat until no such adjacent pair remains. Return the final reduced string.

Implement:

def reduce(s):
    ...

where s is a string over the alphabet {A, B, C, D}. Return the irreducible string that results after no more removals are possible. The result is unique: it does not depend on the order in which you remove pairs.

Constraints: $0 \le \lvert s \rvert \le 2.5 \cdot 10^5$.

Example: s = "CBACD". The pair "CD" at the end cancels, giving "CBA"; then the pair "BA" cancels, giving "C". No further move applies, so the answer is "C".

Further examples: reduce("CABABD") == "" (CABABD to CABD to CD to ""), and reduce("ACBDACBD") == "ACBDACBD" (no adjacent removable pair exists, so nothing is removed).

Show hint

Reduce an example by hand from left to right: what do you need to remember about the part you have already processed?

Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.

Related free problems