โ†ฉ๏ธ

Undo/Redo

Build undo and redo for a text editor using two stacks.

Project 10Advanced

๐Ÿงฉ Problem statement

Process commands: “type:TEXT” (append TEXT), “undo”, “redo”. Show the final text. A new type command clears the redo history. Undo or redo with nothing to undo/redo does nothing.

๐Ÿ“‹ Requirements

  • Type text
  • Undo
  • Redo
  • History view (extension)

๐Ÿ“ฅ Inputs

  • COMMANDS: list of commands

๐Ÿ“ค Outputs

  • The final text

๐Ÿ“ Rules

  • A new action clears the redo stack

๐Ÿšง Constraints

  • Up to hundreds of actions

๐Ÿงญ Suggested approach

  • UNDO stack stores previous versions of the text
  • REDO stack stores undone versions
  • Undo: push current to REDO, pop from UNDO

๐Ÿง  Required concepts

  • Stacks
  • Strings
โœ๏ธ Pseudocode editor ยท dry-run tool ยท test cases

Design your solution here. Use Run to dry-run it step by step and Run tests to check it. Hints unlock one at a time โ€” try on your own first!

๐Ÿงช Edge cases to test

  • Undo with nothing to undo
  • Redo after a new type command (must do nothing)
  • Many undos in a row

๐Ÿ“ˆ Complexity analysis

Each command is O(1) (plus copying the text). Memory O(n) versions.

๐Ÿ“– Solution walkthrough (open after youโ€™ve tried!)

Two stacks hold the past and the undone future. Typing saves the current version on UNDO and wipes REDO, because a new action creates a new timeline. Undo moves the current version to REDO and restores the latest saved one; redo does the opposite. Empty stacks are guarded so extra undos are harmless.

๐Ÿš€ Challenge extensions

  • Limit the history to the last 50 actions
  • Add a delete command
  • Show the undo history list

โ† All projects