DSA Factory
Free lessonsStacks and queues · Stage 0 · Last in, first out · Step 2

Typing with backspace

Build text with a stack; backspace pops the last character. About 8 minutes.

The screen is a stack

Each letter you type lands at the end of the text, and backspace deletes the last character, the newest one. That is push and pop again, like adding and removing plates from a pile.

This time the stack isn't a helper on the side: it is the text on the screen itself.

A letter: push it onto the end.
A hash mark: pop the last character, if there is one.
In code
screen = []
for key in keys:
    if key == "#":
        if screen:
            screen.pop()
    else:
        screen.append(key)
return "".join(screen)
keys = "cat#r##ow"
c
0
a
1
t
2
#
3
r
4
#
5
#
6
o
7
w
8
key
screen
"cat"

c, a, t: each letter is pushed onto the end of the screen.

Move 1 of 6

A stack of characters that turns into a string

In Python, keep a list of characters and join it at the end, and do the same in JavaScript with an array. In Java, a StringBuilder works as a stack: append adds, and deleting the last character removes. In C++, a string already is one, with push-back and pop-back.

The reason to avoid rebuilding the text each time is that it copies every character again.

Python and JavaScript: a list of characters, then join.
Java StringBuilder and C++ string: add and remove at the end.
Don't rebuild the text: cutting off the last character copies the whole text every time.
Quick check

What's left on the screen after these keys?

keys = "ab#c#d"
  1. A"ad"
  2. B"abd"
  3. C"d"
Show the answer

"ad". a, ab, a, ac, a, ad. Each # removes the newest character.

Your problem

Typed with backspaces

keys lists every key someone pressed, in order. Letters are typed as normal. A '#' is the backspace key: it deletes the last character on the screen, or does nothing if the screen is empty. Return the text left on the screen at the end.

Example
keys = "cat#r##ow" → "cow"

0 ≤ length of keys ≤ 100,000 · keys has lowercase letters and #

Solve it in your browserPython, C++, Java or JavaScript. Hints if you get stuck. No sign-up needed.
Start coding