Typing With Backspace
EasyStackFree
Problem
An old terminal records every key press in a string keys. Lowercase letters are typed characters and # is the backspace key: it erases the character just before the cursor, if there is one. Backspace on an empty line does nothing.
Return the text left on the line after all key presses.
Example 1
- Input:
- keys = "ab#c"
- Output:
- "ac"
Type a, b; backspace erases b; type c.
Example 2
- Input:
- keys = "##x#"
- Output:
- ""
The first two backspaces hit an empty line; x is typed and then erased.
Example 3
- Input:
- keys = "abc##d#e"
- Output:
- "ae"
Constraints
- 0 ≤ keys.length ≤ 10^5
- keys contains lowercase letters and '#'
Hint
Show the first hint
A backspace always removes the most recently typed surviving character.
Walkthrough
How to approach it
01Clarify before coding
- What does '#' do on an empty line? Nothing; it must not crash.
- Can the result be empty? Yes, return the empty string.
- Are there other special keys? No, only '#'.
02Brute force
Keep the result as an immutable string and rebuild it on every key: text = text + c or text = text[:-1].
Cost: Each rebuild copies the whole current text, so O(n²) time in the worst case for 10^5 keys.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.