Remove adjacent duplicates

Lesson 5.5 · Easy · Undo · 6 min · by Vinay C

We'll cover the following

Repeatedly remove two equal letters that sit next to each other. Return what is left.

Watch it run

Press Play or Step to walk through the example, or change the input and press Run. Each frame says what the algorithm does and why.

pusha0

d10

f11

g12

h13

h14

g15

f16

"a" differs from the top. Push it.

stack "a"

1 / 18

Time	Space	Why
`O(n)`	`O(n)`	Each character is pushed and popped at most once.

def remove_duplicates(s):
    st = []
    for ch in s:
        if st and st[-1] == ch: st.pop()
        else: st.append(ch)
    return ''.join(st)

The stack is your result so far. If the new letter equals the top, they cancel. This pattern of "undo the last thing when the new thing cancels it" shows up in many string problems.
Time O(n), space O(n). Each character is pushed and popped at most once.