Squash Duplicate Neighbors

L4 Easy Stack

Concept

When a character must be removed and its neighbors then become adjacent, a stack does the job: push characters, and pop whenever the next character matches the top.

Given a string s, repeatedly remove adjacent equal pairs. Removing a pair can make two new characters adjacent, which may form another pair — keep going until no adjacent equal pairs remain. Return the final string.

Examples

▸ s = "abbaca"

→ ca

▸ s = "azxxzy"

→ ay

▸ s = "aaaa"

→

Progressive Hints

Hint 1 · Nudge

A stack makes 'removing a pair can expose a new pair' happen automatically.

Hint 2 · Plan

Walk the string pushing characters onto a stack. Whenever the next character equals the character on top of the stack, pop instead of push. The stack left behind is the final string.

Hint 3 · Approach

stack = []. For each c in s: if the stack is non-empty and its top equals c, pop; otherwise push c. Return the stack joined as a string.

Output

// Run your code to see the output here.