DSA Removing Adjacent Duplicates

The problem

Removing adjacent duplicates deletes pairs of equal neighbouring characters. The deletions repeat. The process stops only when no two neighbours are equal.

The input is one string. The output is the reduced string. The output can be empty, when every character cancels.

cases = [
    ("abbaca", "ca"),
    ("azxxzy", "ay"),
    ("aabccb", ""),
    ("abba", ""),
    ("abcd", "abcd"),
]
for text, expected in cases:
    print(text, "->", repr(expected))

Read one row at a time. In abbaca the b pair cancels first, and that exposes an a pair, which cancels too. Only ca survives. In abcd no neighbours match, so nothing changes.

Intuition: one deletion pass is not enough

The first idea is to scan the string once and delete each equal pair on sight. That handles the pairs visible at the start. It misses the pairs that a deletion creates.

A deletion joins two characters that were never neighbours before. Those new neighbours can be equal. Deleting them can join another pair. The chain is called a cascade.

def one_pass(text):
    out = []
    i = 0
    while i < len(text):
        if i + 1 < len(text) and text[i] == text[i + 1]:
            i += 2
        else:
            out.append(text[i])
            i += 1
    return "".join(out)

print("abba after one pass:", repr(one_pass("abba")))
print("abbaca after one pass:", repr(one_pass("abbaca")))

The one pass turns abba into aa and stops. The a pair it created is still there. Any correct method has to react to new pairs the moment they form, not on a later scan.

Brute force: delete and restart

A straightforward method repeats the scan until nothing changes. Find the first equal neighbouring pair. Delete both characters. Start again from the beginning.

The method is correct because it never stops early. Its cost is the restarting: each deletion sends the scan back to index 0, and the surviving prefix is compared again.

def reduce_slow(text):
    chars = list(text)
    comparisons = 0
    changed = True
    while changed:
        changed = False
        for i in range(len(chars) - 1):
            comparisons += 1
            if chars[i] == chars[i + 1]:
                del chars[i:i + 2]
                changed = True
                break
    return "".join(chars), comparisons

for text in ("abbaca", "aabccb", "abcd"):
    result, comparisons = reduce_slow(text)
    print(text, "->", repr(result), "comparisons:", comparisons)

The results match the cases. The comparison counts are the bill: even short strings pay for several restarts, and a long string with late pairs pays far more.

The optimal solution: a stack of survivors

Keep a stack of survivors: a new character cancels the stack top when it matches, and is pushed when it does not. That one rule handles cascades for free, because a cancellation exposes the new top at once.

def reduce_string(text):
    stack = []
    for ch in text:
        if stack and stack[-1] == ch:
            stack.pop()
        else:
            stack.append(ch)
    return "".join(stack)

for text in ("abbaca", "azxxzy", "aabccb", "abba", "abcd"):
    result = reduce_string(text)
    print(text, "->", result if result else "(empty)")

All five cases pass. Joining the stack at the end gives the reduced string in order. The stack never holds an equal neighbouring pair, because a match cancels instead of pushing.

Walkthrough: abbaca, character by character

Watch the survivor stack grow and shrink. A push adds the character on the right of the printed list. A cancellation removes the top instead.

def reduce_traced(text):
    stack = []
    for ch in text:
        if stack and stack[-1] == ch:
            stack.pop()
            action = "cancels the top"
        else:
            stack.append(ch)
            action = "is pushed"
        print("char", ch, action, "-> stack", stack)
    return "".join(stack)

print("result:", repr(reduce_traced("abbaca")))

The second b cancels the first. The third character, a, then meets the a at the bottom and cancels it. The last two characters meet no match and survive as ca.

Complexity

Time is O(n) for a string of length n: each character is pushed once and popped at most once, so the total work grows in step with the input.

Space is O(n) in the worst case: a string with no equal neighbours keeps every character on the stack.

def count_work(text):
    stack = []
    pushes = 0
    pops = 0
    for ch in text:
        if stack and stack[-1] == ch:
            stack.pop()
            pops += 1
        else:
            stack.append(ch)
            pushes += 1
    return pushes, pops

for text in ("abcd", "aabbcc", "abbaca", "aaaaaaaa"):
    pushes, pops = count_work(text)
    print(text, "length:", len(text), "pushes:", pushes, "pops:", pops)

Pushes plus pops never exceed twice the length. Even the all-same string, the worst cascade, stays inside that bound. The restarting method has no such small bound.

Edge cases and pitfalls

An empty input gives an empty output. The loop never runs and the join of an empty stack is the empty string.

An odd run of one character leaves one survivor. Pairs cancel two at a time, so aaa reduces to a, while aaaa reduces to nothing.

def reduce_string(text):
    stack = []
    for ch in text:
        if stack and stack[-1] == ch:
            stack.pop()
        else:
            stack.append(ch)
    return "".join(stack)

print("empty:", repr(reduce_string("")))
print("single:", repr(reduce_string("x")))
print("three of a kind:", repr(reduce_string("aaa")))
print("four of a kind:", repr(reduce_string("aaaa")))
print("no pairs:", repr(reduce_string("abca")))

One pitfall hides in the guard. The stack check must come before the top comparison. Reading stack[-1] on an empty stack raises an error instead of pushing the first character.