A tiny editor starts with an empty document. Write run_editor(commands: list[str]) -> str that applies the commands in order and returns the final text.
"type <word>"addswordto the end of the text.wordis one or more lowercase letters."delete <k>"removes the lastkcharacters (k >= 1). If the text is shorter thank, it removes all of it."undo"cancels the most recenttypeordeletethat hasn't been undone yet, so the text goes back to how it was before that edit. With nothing left to undo, it does nothing.
An undo is never undone itself: there is no redo.
run_editor(["type abc", "type de", "undo"]) # "abc"
run_editor(["type hello", "delete 2", "type p", "undo", "undo"]) # "hello"
# "hello" -> "hel" -> "help" -> undo the type: "hel" -> undo the delete: "hello"
run_editor(["type ab", "delete 5", "undo"]) # "ab"
run_editor(["undo", "type x"]) # "x"
Constraints: up to 2 * 10^5 commands; at most 2 * 10^5 letters typed in total; the k values of all delete commands add up to at most 2 * 10^5. Saving a full copy of the text before every edit is O(commands × length), which fails the large test. Aim for work proportional to the input.
Show hint
keep a stack (a Python list) of past edits, newest on top. For each edit, push only what you need to reverse it: for type, how many letters were added; for delete, the letters that were removed. undo pops the top entry and reverses it. Keeping the text itself as a list of characters makes adding and removing at the end cheap.