Implement undo/redo with two stacks

Problem: Undo/Redo for a Simple Text Editor

Design a data structure that simulates a very small text editor with undo and redo.

You are given a sequence of commands; after each command, output the current text.

Commands

• TYPE s : append string s to the end of the current text.
• DELETE k : delete the last k characters (if k exceeds current length, delete everything).
• UNDO : undo the most recent mutating command ( TYPE or DELETE ) that has not already been undone.
• REDO : redo the most recent undone command, if no new mutating command has occurred since the undo.

Notes / Rules

• UNDO / REDO that cannot be applied should do nothing.
• Any new TYPE / DELETE after an UNDO clears the redo history.

Input / Output

• Input: a list of commands in the format above.
• Output: the editor text after each command.

Example

Commands:

1. TYPE abc
2. TYPE d
3. DELETE 2
4. UNDO
5. REDO

Outputs:

1. abc
2. abcd
3. ab
4. abcd
5. ab

Constraints (typical)

• Up to $2\times 10^5$ commands.
• Total typed characters across all TYPE commands up to $2\times 10^5$ .