An antique typewriter has a mechanical fault in its number-key row. Every time a digit key ('0'-'9') is struck, the fault immediately strikes out that digit AND the closest earlier letter that has not already been struck out (that is, the nearest surviving letter to its left among everything typed so far). If, at the moment a digit is struck, there is no surviving letter anywhere to its left, only the digit itself is struck out and nothing else changes. Letters are never struck out for any other reason.
Given the full sequence of keys that were pressed, determine exactly what text remains legible on the page after every key in the sequence has been struck and every resulting strike-out has been applied.
A single line containing the string s of keys that were pressed, consisting only of lowercase English letters ('a'-'z') and digits ('0'-'9').
A single line containing the surviving text (print an empty line if nothing survives).
Example 1
Input
abcd12
Expected
ab
Explanation
Letters a, b, c, d are typed and survive so far: [a,b,c,d]. The digit '1' strikes out itself and the nearest surviving letter to its left, 'd', leaving [a,b,c]. The digit '2' strikes out itself and 'c', leaving [a,b]. The final surviving text is "ab".
Example 2
Input
1a2b
Expected
b
Explanation
The digit '1' is struck first, but there is no surviving letter to its left yet, so only the '1' is discarded. Letter 'a' survives: [a]. The digit '2' strikes out itself and the nearest surviving letter 'a', leaving []. Letter 'b' survives: [b]. The final surviving text is "b".
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →