Free Recursion lessonsRecursion · Stage 1 · Lists and strings · Step 3

Cancel neighbouring twins

Build the answer for a string from the answer for its shorter tail, fixing up the front on the way back. About 13 minutes.

Solve the tail first

Take a string like "abbaca". Whenever two equal letters sit side by side, they cancel, and the rest closes up. Cancelling can chain: "abba" loses the middle "bb" and then the outer "aa".

To handle the chains, use recursion on the tail: first collapse everything after the first letter. That answer is already fully cancelled. Now the only thing left to check is whether the first letter matches the front of that answer. If it does, they cancel. If not, put the first letter on the front.

Collapse the rest first, it comes back fully cancelled.

Then compare: the first letter with the front of the answer.

In code

def collapse(s):
    if s == "":
        return ""
    rest = collapse(s[1:])
    if rest and rest[0] == s[0]:
        return rest[1:]
    return s[0] + rest

Collapse a, b, b, a, c, a from the right.

leftright

The tail from the last letter: just a. Nothing to cancel, so the answer is a.

Move 1 of 6

Why one comparison is enough

After collapsing, the tail has no equal neighbours at all. So if you put the first letter in front, the only possible equal pair is the first letter with the new second letter, which is the front of the tail's answer.

That is why you only compare the first letter with the front of the answer, and never need to look further in. The base case is the empty string, which has nothing to cancel.

Tail has no twins: so only the front can match.

Base case: the empty string stays empty.

Quick check

The answer for the tail is "bca" and the first letter is b. What does the whole answer become?

A"ca", because the two b's cancel
B"bbca"
C"bca"

Show the answer

"ca", because the two b's cancel. The first letter matches the front of the tail's answer, so both disappear.

Your problem

Cancel neighbouring twins

s is a string of lowercase letters. Whenever two equal letters are next to each other, they cancel and both disappear, and the letters around them close up (which can create new neighbouring twins). Keep cancelling until no twins are left. Return the final string, which may be empty.

Example

s = "abbaca" → "ca"

0 ≤ length ≤ 500 · lowercase letters

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.