Star as Backspace

Medium

On an old keyboard the Backspace key is broken and types * instead. You are given the string typed, everything that was typed, in order. Each * erases the closest letter to its left that has not been erased yet, and disappears itself. Every star is guaranteed to have something to erase. Return the final text, a string with no stars.

Example 1

typed='cat*r**ow' → 'cow'

cat → * erases t → car → two * erase r and a → c → then ow is typed. The result is cow.

Example 2

typed='no**' → ''

Both letters are erased, leaving an empty string.

Example 3

typed='hello' → 'hello'

Constraints

1 ≤ len(typed) ≤ 10⁶
typed consists of lowercase English letters and *
No prefix of typed has more stars than letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Stack String Simulation

Similar problems

Erase the Pattern Until It Is Gone Medium Crashes on One Lane Medium Mirror Letter Pairing Score Medium Same Text After Erasing Easy Collapse Letter Pairs Easy

Input

typed='cat*r**ow'

Expected

'cow'

Run checks the first 3 tests in your browser. Submit checks all 68 tests on the server, hidden ones included.