Cancel out the doubled keystrokes
A faulty keyboard doubles a letter now and then. The cleaner removes any two identical letters sitting next to each other, and keeps going while that leaves a new pair behind.
- Two identical characters next to each other both disappear.
- Removing a pair can bring two more together, and those go too.
- Keep going until no adjacent pair is left.
- Text with nothing to remove comes back unchanged.
collapse_doubles(typed: string) → string
Where you start
def collapse_doubles(typed: str) -> str:
Worked examples
| Call | Result |
|---|---|
collapse_doubles("abbaca") | "ca" |
collapse_doubles("azxxzy") | "ay" |
collapse_doubles("abc") | "abc" |
collapse_doubles("aa") | "" |
Hint
Build the result on a stack. For each character, either it cancels the one on top or it goes on top — no rescanning needed.
Reference solution in Python
def collapse_doubles(typed: str) -> str:
kept = []
for ch in typed:
if kept and kept[-1] == ch:
kept.pop()
else:
kept.append(ch)
return "".join(kept)