063. Remove Adjacent Equal Pairs

Foundation · Download this solution · All solutions and shared helpers

Problem

Repeatedly remove adjacent equal character pairs until no such pair remains, and return the remaining string. Characters are case-sensitive. Removing a pair may expose a new pair across its former boundary. Empty input returns an empty string.

Examples

Example 1

remove_adjacent_pairs("abbaca")
=> 'ca'

Removing bb exposes aa, which also disappears.

Example 2

remove_adjacent_pairs("aaaa")
=> ''

Two cancellations remove all four characters.

Example 3

remove_adjacent_pairs("")
=> ''

The reduced empty prefix is empty.

Reveal the worked solution and reasoning

Why this mechanism works

Keep the already reduced prefix on a stack. An incoming character can create a new removable pair only with that prefix's final character. A match pops it; otherwise the new character remains unresolved at the top. This simulates cascading removals without rescanning the whole string.

State and boundaries

stack is the fully reduced form of the consumed prefix and has no adjacent equal pair.

Protocol

Compare the incoming character with the stack top.
Pop on equality.
Otherwise push the character.
Join the stack after the scan.

Visualization

abbaca
abb -> a
aa -> empty
remaining ca -> ca

Python implementation

def remove_adjacent_pairs(text):
    stack = []
    for char in text:
        if stack and stack[-1] == char:
            stack.pop()
        else:
            stack.append(char)
    return ''.join(stack)

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

remove_adjacent_pairs("abbaca")

L2 remove_adjacent_pairs: stack = []
text='abbaca'; stack=[]

L3 remove_adjacent_pairs: for char in text:
text='abbaca'; stack=[]; char='a'

L7 remove_adjacent_pairs: stack.append(char)
text='abbaca'; stack=['a']; char='a'

L3 remove_adjacent_pairs: for char in text:
text='abbaca'; stack=['a']; char='b'

L7 remove_adjacent_pairs: stack.append(char)
text='abbaca'; stack=['a', 'b']; char='b'

L5 remove_adjacent_pairs: stack.pop()
text='abbaca'; stack=['a']; char='b'

L3 remove_adjacent_pairs: for char in text:
text='abbaca'; stack=['a']; char='a'

L5 remove_adjacent_pairs: stack.pop()
text='abbaca'; stack=[]; char='a'

L3 remove_adjacent_pairs: for char in text:
text='abbaca'; stack=[]; char='c'

L7 remove_adjacent_pairs: stack.append(char)
text='abbaca'; stack=['c']; char='c'

L3 remove_adjacent_pairs: for char in text:
text='abbaca'; stack=['c']; char='a'

L7 remove_adjacent_pairs: stack.append(char)
text='abbaca'; stack=['c', 'a']; char='a'

Result: 'ca'. Removing bb exposes aa, which also disappears.

remove_adjacent_pairs("aaaa")

L2 remove_adjacent_pairs: stack = []
text='aaaa'; stack=[]

L3 remove_adjacent_pairs: for char in text:
text='aaaa'; stack=[]; char='a'

L7 remove_adjacent_pairs: stack.append(char)
text='aaaa'; stack=['a']; char='a'

L5 remove_adjacent_pairs: stack.pop()
text='aaaa'; stack=[]; char='a'

L7 remove_adjacent_pairs: stack.append(char)
text='aaaa'; stack=['a']; char='a'

L5 remove_adjacent_pairs: stack.pop()
text='aaaa'; stack=[]; char='a'

Result: ''. Two cancellations remove all four characters.

Why the solution is correct

The reduced prefix has no internal removable pair. Appending one character can create a pair only at its boundary, and popping that pair restores the reduced-prefix property. Repeating this transition yields a fully reduced result for the whole input.

Time and space

O(n) time and O(n) stack/output space.

Common mistakes

Removing only pairs present in the original string misses cascades. Popping without checking emptiness fails on the first character.

Reasoning card

State: stack is the fully reduced form of the consumed prefix and has no adjacent equal pair.

Invariant: Stack is the fully reduced processed prefix.

Decision to rehearse: Stack top is the unresolved neighbour of the incoming character.

Finish: Join the stack after the scan

Transfer exercise

Remove runs of exactly k equal characters by storing a character and an active count per stack entry.