Apply the backspaces in typed text

Stacks and queues Junior Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
typed = "ab##c#d"
stack: list[str] = []
for ch in typed:
    if ch == "#":
        if stack:
            stack.pop()
    else:
        stack.append(ch)
print("".join(stack))

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A d

Right: a and b are erased, c is erased, d remains.

Every backspace undoes the most recent character, which is exactly what popping a stack does.

Why not the others?
  • B cd. The third '#' erases the c.
  • C abcd. Each '#' removes the latest kept character.

30-second answer

Use a list as a stack of characters: push normal characters, pop on '#' when the stack is not empty. Join at the end. O(n) time and space. Reading from the right with a skip counter gives O(1) extra space if you only need to compare two logs.

Practise saying it · 30 s. No recording, just a timer

Explain how to apply backspaces.

Say your answer out loud, then check which of these points you covered:

  • Stack of characters
  • Pop on '#'
  • Join at the end

Deep dive

The stack is the natural model for undo: the most recent action is undone first.

Building the result with ''.join keeps it linear.

Comparing two logs from the right with skip counters avoids building either string.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def apply_backspaces(typed: str) -> str:
    kept: list[str] = []
    for ch in typed:
        if ch != "#":
            kept.append(ch)
        elif kept:
            kept.pop()
    return "".join(kept)

Common mistakes

  • Popping from an empty stack when the log starts with '#'.
  • Building the result with string slicing, which is O(n²) in the worst case.

Senior take & follow-ups

Mention the O(1)-space comparison follow-up even if you code the stack version.

Follow-up questions

Think of your answer first, then open the hint.

  1. How would you compare two logs in O(1) extra space?

    Show hint

    Walk both from the end, skipping characters covered by backspaces, and compare as you go.

  2. What about a 'delete word' key?

    Show hint

    Pop until a space or the empty stack.

What each operation costs: Stack · Queue · Deque

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.