Loading…

mediumStack QueueSometimes asked

Simple Text Editor

Q: How do you solve Simple Text Editor using the Stack of Full State Snapshots (Clear and Correct) approach?

When to use it: The straightforward, interview-safe answer. Note it's the simplest correct model and that snapshots can be memory-heavy. Keep `S` and a `history` stack of previous values of `S`. **Snapshot before mutating.** On an append (`1 W`) or delete (`2 k`), first push the *current* `S` onto `history`, then perform the change. The snapshot captures the state to which undo must return. **Undo pops.** On `4`, pop `history` and assign it back to `S`. Because we pushed exactly once per mutation, each undo reverses exactly one mutation, in reverse order — the LIFO discipline matches 'undo the last operation'. **Print reads only.** On `3 k`, output `S[k-1]` (1-indexed). This neither pushes nor pops; undo must not revert a print, so prints leave the history untouched. Likewise, undo itself doesn't push — it consumes history rather than adding to it. **Why snapshot before, not after.** Undo needs the state *prior* to the change. If you snapshotted after mutating, you'd save the post-change state and undo would do nothing. The order is: save old, then change. **Memory note.** Full snapshots are the simplest correct approach but can store many copies. For tight memory, store inverse operations instead (see insight): undoing an append removes the appended suffix; undoing a delete re-appends the deleted suffix. That keeps O(1) extra data per operation. Time complexity: O(1) undo, O(|W|) append, O(1) delete (amortised). Space complexity: O(total characters across snapshots).

Q: How do you solve Simple Text Editor using the Stack of Inverse Operations (Memory-Optimised) approach?

When to use it: Bring up when memory matters at q = 10⁶: store how to reverse each op instead of full copies. Rather than snapshotting the entire string, record the *inverse* of each mutation so undo can replay it backward. **Append inverse.** When you append `W`, the only way to undo it is to remove the last `|W|` characters. So push a record like `('A', W.length())`. Undo reads it and deletes that many characters from the end. **Delete inverse.** When you delete the last `k` characters, undo must put them back. So before deleting, capture the removed suffix and push `('D', removedSuffix)`. Undo re-appends that suffix. **Why this saves memory.** The full-snapshot approach can store O(|S|) per mutation, so a long string mutated many times costs O(q·|S|). The inverse-op approach stores only the change each time — a length or a short substring — so total storage is bounded by the total volume of text ever appended or deleted, independent of how long `S` grows. This matters at q up to 10⁶. **Same stack discipline.** Push on mutate, pop on undo, never on print. Only the payload changes from 'whole state' to 'how to reverse this step'. Time complexity: O(1) undo, O(|W|) append, O(1) delete. Space complexity: O(total characters) but only the deltas, not full snapshots.

Stack & Queue · 14 of 17 · 9 min

Implement a simple text editor over an initially empty string S. Process q operations of four types:

1 W — append the string W to the end of S.
2 k — delete the last k characters of S.
3 k — print the k-th character of S (1-indexed).
4 — undo the last not-yet-undone append or delete, reverting S to its previous value.

Print the result of each type-3 operation on its own line.

In plain English

There are two mutating operations (append, delete) and two read-only ones (print, undo-restore). To undo we must remember what `S` looked like before each mutation. A stack of previous states (or of inverse operations) gives last-in-first-out reverts, which is exactly what 'undo the last operation' means.

Examples

Example 1

Input: ops = ["1 abc", "3 3", "2 3", "1 xy", "3 2", "4", "4", "3 1"]
Output: c y a
Note: After '1 abc' S='abc' (print 3rd='c'). '2 3' → S=''. '1 xy' → S='xy' (print 2nd='y'). undo → S=''. undo → S='abc' (print 1st='a').

Example 2

Input: ops = ["1 abcde", "1 fg", "3 7", "4", "3 5"]
Output: g e
Note: S='abcde' then 'abcdefg' (7th='g'). undo reverts the second append → S='abcde' (5th='e').

Example 3

Input: ops = ["1 xy", "2 1", "3 1", "4", "3 2"]
Output: x y
Note: S='xy', delete 1 → 'x' (1st='x'). undo restores 'xy' (2nd='y').

Constraints

1 ≤ q ≤ 10⁶
1 ≤ k ≤ |S| for delete and print operations
Total length of all appended strings ≤ 10⁶
Every type-4 (undo) has a matching prior append or delete to revert
Operations should be efficient (amortised near O(1) per op, O(length) per append)

Clarifying questions4First question: Does undo revert exactly one operation, or everything?Explore questions

Q1.Does undo revert exactly one operation, or everything?
Exactly one — the most recent append or delete that hasn't been undone yet. That LIFO behaviour is why a stack fits.
Q2.Are print and undo themselves undoable?
No. Only append and delete mutate S and are undoable. Print is read-only, and undo is the mechanism, not a tracked operation.
Q3.Is the print index 1-based or 0-based?
1-based. The k-th character is at index k−1 in a 0-indexed string.
Q4.Could the snapshots be large? Any memory concern?
Storing full string copies is simplest but can be memory-heavy. The leaner option stores inverse operations: for an append, record 'remove the appended suffix'; for a delete, record the deleted suffix to re-append.

Stack & Queue

Progress14/17

DifficultyMedium

OptimalO(1) undo, O(|W|) append, O(1) delete · O(total characters) but only the deltas, not full snapshots

FrequencySometimes asked

Read9–11 min

Asked at

AmazonMicrosoftGoogleBloombergAdobe

In this module

PrevMin Max Riddle NextTruck Tour

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Implement undo by pushing the current text onto a stack BEFORE every mutating operation (append or delete). Undo simply pops and restores the previous snapshot. Append and delete each run in O(length of change) using StringBuilder/list, and undo is O(1) by swapping in the saved state. Print indexes the current text directly.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you model undo with a stack of prior states (or inverse operations) and correctly snapshot only on mutating operations, with clean 1-indexed access.

Where candidates slip

Pushing history on print/undo too (corrupting the undo chain), snapshotting AFTER the mutation, or using 0-indexed access for the 1-indexed print query.

How to stand out

State the 'push current state before mutating' invariant, note undo is O(1), and mention the memory-leaner alternative of storing inverse operations rather than full string copies.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Stack of Full State Snapshots (Clear and Correct)	`O(1) undo, O(\|W\|) append, O(1) delete (amortised)`	`O(total characters across snapshots)`	The straightforward, interview-safe answer. Note it's the simplest correct model and that snapshots can be memory-heavy.	Read
2	Stack of Inverse Operations (Memory-Optimised)Optimal	`O(1) undo, O(\|W\|) append, O(1) delete`	`O(total characters) but only the deltas, not full snapshots`	Bring up when memory matters at q = 10⁶: store how to reverse each op instead of full copies.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewoperationtype?1 W (append)2 k (delete)Explore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Stack of Full State Snapshots (Clear and Correct)

TimeO(1) undo, O(|W|) append, O(1) delete (amortised)SpaceO(total characters across snapshots)

The straightforward, interview-safe answer. Note it's the simplest correct model and that snapshots can be memory-heavy.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Undo reverts the most recent mutation. What data structure gives last-in-first-out access to past states?

2Hint 2Explore hint

Before each append or delete, push the current string onto a stack. Then mutate.

3Hint 3Explore hint

Undo pops the stack and assigns the popped state back to S. Print and undo never push.

A · Core idea

Keep S and a history stack of previous values of S.

Snapshot before mutating. On an append (1 W) or delete (2 k), first push the current S onto history, then perform the change. The snapshot captures the state to which undo must return.

Undo pops. On 4, pop history and assign it back to S. Because we pushed exactly once per mutation, each undo reverses exactly one mutation, in reverse order — the LIFO discipline matches 'undo the last operation'.

Print reads only. On 3 k, output S[k-1] (1-indexed). This neither pushes nor pops; undo must not revert a print, so prints leave the history untouched. Likewise, undo itself doesn't push — it consumes history rather than adding to it.

Why snapshot before, not after. Undo needs the state prior to the change. If you snapshotted after mutating, you'd save the post-change state and undo would do nothing. The order is: save old, then change.

Memory note. Full snapshots are the simplest correct approach but can store many copies. For tight memory, store inverse operations instead (see insight): undoing an append removes the appended suffix; undoing a delete re-appends the deleted suffix. That keeps O(1) extra data per operation.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

ops = ["1 abc", "3 3", "2 3", "1 xy", "3 2", "4", "4", "3 1"]

Array state

after 1 abc

S='abc', history=['']

[0]

Current pointerResolved stateNot processed

Final result

c
y
a

C · Code with teaching comments

Reference implementation previewimport java.util.*; public List<Character> simpleTextEditor(String[] ops) { StringBuilder s = new StringBuilder(); Deque<String> history = new ArrayDeque<>();Explore the full code

solution.javaJava

Stack of Full State Snapshots (Clear and Correct) — reference

5 teaching notes

1
import java.util.*;
2
 
3
public List<Character> simpleTextEditor(String[] ops) {
4
    StringBuilder s = new StringBuilder();
5
    Deque<String> history = new ArrayDeque<>();
6
    List<Character> out = new ArrayList<>();
7
    for (String op : ops) {
8
        if (op.charAt(0) == '1') {
9
            String w = op.substring(2);
10
            // Snapshot the CURRENT state before appending — this is what undo restores.
11
            history.push(s.toString());
12
            // Append the new text after snapshotting.
13
            s.append(w);
14
        } else if (op.charAt(0) == '2') {
15
            int k = Integer.parseInt(op.substring(2).trim());
16
            history.push(s.toString());
17
            // Delete the last k characters (snapshot was already pushed).
18
            s.delete(s.length() - k, s.length());
19
        } else if (op.charAt(0) == '3') {
20
            int k = Integer.parseInt(op.substring(2).trim());
21
            // Print is 1-indexed → charAt(k-1); no history change.
22
            out.add(s.charAt(k - 1));
23
        } else {
24
            // Undo: restore the most recent snapshot. O(1) stack pop.
25
            s = new StringBuilder(history.pop());
26
        }
27
    }
28
    return out;
29
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.29 lines

D · Why it works and complexityO(1) undo, O(|W|) append, O(1) delete (amortised) timeO(total characters across snapshots) spaceOpen the invariant and proofExplore the proof

Undo = 'push the old state before you change it, pop to go back'. The memory-optimal twist is to push what to do to reverse the op rather than the whole state: store the length appended (to chop it off) or the substring deleted (to glue it back). Same stack, smaller payload — the Command pattern's reversible-command idea.

ComplexityO(1) undo, O(|W|) append, O(1) delete (amortised) time, O(total characters across snapshots) space — Each mutating op does one push (snapshot) and the mutation; undo is a single pop and assignment → O(1). Space is the sum of snapshot lengths kept on the stack.

E · Edge cases and pitfalls6delete everything then undo — '2 k' with k = |S| pushes the full string and empties S; undo restores it fully.Explore edge cases

Edge cases handled

delete everything then undo'2 k' with k = |S| pushes the full string and empties S; undo restores it fully.
undo right after an appendPops the pre-append snapshot, removing exactly the appended text.

Pitfalls

Pushing a snapshot on print or undo — corrupts the undo chain.
Snapshotting AFTER mutating instead of before — undo then restores the wrong state.
0-indexing the print query — the k-th character is at index k−1.
Re-building S from a copied string per character append can be O(n²) — use StringBuilder/list.

03.2

Approach 2 of 2 · Optimal

Stack of Inverse Operations (Memory-Optimised)

TimeO(1) undo, O(|W|) append, O(1) deleteSpaceO(total characters) but only the deltas, not full snapshots

Bring up when memory matters at q = 10⁶: store how to reverse each op instead of full copies.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Instead of saving the whole string before each change, save just what's needed to reverse that one change.

2Hint 2Explore hint

To undo an append of W, you only need to chop |W| characters off the end. To undo a delete of the last k chars, you need those k characters back.

3Hint 3Explore hint

Push a small record per mutation: ('append', len) or ('delete', removedSubstring). Undo applies the inverse.

A · Core idea

Rather than snapshotting the entire string, record the inverse of each mutation so undo can replay it backward.

Append inverse. When you append W, the only way to undo it is to remove the last |W| characters. So push a record like ('A', W.length()). Undo reads it and deletes that many characters from the end.

Delete inverse. When you delete the last k characters, undo must put them back. So before deleting, capture the removed suffix and push ('D', removedSuffix). Undo re-appends that suffix.

Why this saves memory. The full-snapshot approach can store O(|S|) per mutation, so a long string mutated many times costs O(q·|S|). The inverse-op approach stores only the change each time — a length or a short substring — so total storage is bounded by the total volume of text ever appended or deleted, independent of how long S grows. This matters at q up to 10⁶.

Same stack discipline. Push on mutate, pop on undo, never on print. Only the payload changes from 'whole state' to 'how to reverse this step'.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

ops = ["1 abcde", "1 fg", "3 7", "4", "3 5"]

Array state

after appends

S='abcdefg', history=[('A',5),('A',2)]

A:5

[0]

A:2

[1]

Current pointerResolved stateNot processed

Final result

g
e

C · Code with teaching comments

solution.javaJava

Stack of Inverse Operations (Memory-Optimised) — optimal

6 teaching notes

1
import java.util.*;
2
 
3
public List<Character> simpleTextEditor(String[] ops) {
4
    StringBuilder s = new StringBuilder();
5
    Deque<int[]> appendLog = new ArrayDeque<>();   // marker for append: {1, len}
6
    Deque<String> deleteLog = new ArrayDeque<>();   // removed suffixes
7
    Deque<Integer> typeLog = new ArrayDeque<>();    // 1 = append, 2 = delete
8
    List<Character> out = new ArrayList<>();
9
    for (String op : ops) {
10
        if (op.charAt(0) == '1') {
11
            String w = op.substring(2);
12
            s.append(w);
13
            // To undo an append, we only need to know how many chars to chop.
14
            appendLog.push(new int[]{w.length()});
15
            typeLog.push(1);
16
        } else if (op.charAt(0) == '2') {
17
            int k = Integer.parseInt(op.substring(2).trim());
18
            // Capture the suffix BEFORE deleting so undo can restore it.
19
            String removed = s.substring(s.length() - k);
20
            s.delete(s.length() - k, s.length());
21
            // Record the removed text as the delete's inverse payload.
22
            deleteLog.push(removed);
23
            typeLog.push(2);
24
        } else if (op.charAt(0) == '3') {
25
            int k = Integer.parseInt(op.substring(2).trim());
26
            out.add(s.charAt(k - 1));
27
        } else {
28
            // Undo: find out whether the last mutation was an append or delete.
29
            int t = typeLog.pop();
30
            if (t == 1) {
31
                int len = appendLog.pop()[0];
32
                // Undo append by removing the appended suffix.
33
                s.delete(s.length() - len, s.length());
34
            } else {
35
                String removed = deleteLog.pop();
36
                // Undo delete by re-appending the captured suffix.
37
                s.append(removed);
38
            }
39
        }
40
    }
41
    return out;
42
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.42 lines

D · Why it works and complexityO(1) undo, O(|W|) append, O(1) delete timeO(total characters) but only the deltas, not full snapshots spaceOpen the invariant and proofExplore the proof

This is the Command pattern: every mutation is a reversible command that knows how to undo itself. Snapshots trade memory for simplicity; inverse operations trade a little code for big memory savings. Recognising both lets you pick based on constraints.

ComplexityO(1) undo, O(|W|) append, O(1) delete time, O(total characters) but only the deltas, not full snapshots space — Each mutation pushes a small delta record. Undo pops it and applies the inverse in O(size of that delta). Total stored data is bounded by total characters appended/deleted, not multiplied by string length.

E · Edge cases and pitfalls5undo an append of length |S| — Chops the entire appended block, returning S to its pre-append value.Explore edge cases

Edge cases handled

undo an append of length |S|Chops the entire appended block, returning S to its pre-append value.
undo a full deleteRe-appends the whole captured suffix, restoring S exactly.

Pitfalls

Capturing the deleted suffix AFTER deleting — it's already gone; capture before.
Forgetting to record the operation type, so undo can't tell append from delete.
Mismatched logs (separate stacks drifting) — a single stack of tagged records is safer.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewimport java.util.*; public List<Character> simpleTextEditor(String[] ops) { StringBuilder s = new StringBuilder(); Deque<int[]> appendLog = new ArrayDeque<>(); // marker for append: {1, len}Explore the playground

Try it — Java· run a complete program; method snippets need a driver

import java.util.*;

public List<Character> simpleTextEditor(String[] ops) {
    StringBuilder s = new StringBuilder();
    Deque<int[]> appendLog = new ArrayDeque<>();   // marker for append: {1, len}
    Deque<String> deleteLog = new ArrayDeque<>();   // removed suffixes
    Deque<Integer> typeLog = new ArrayDeque<>();    // 1 = append, 2 = delete
    List<Character> out = new ArrayList<>();
    for (String op : ops) {
        if (op.charAt(0) == '1') {
            String w = op.substring(2);
            s.append(w);
            appendLog.push(new int[]{w.length()});
            typeLog.push(1);
        } else if (op.charAt(0) == '2') {
            int k = Integer.parseInt(op.substring(2).trim());
            String removed = s.substring(s.length() - k);
            s.delete(s.length() - k, s.length());
            deleteLog.push(removed);
            typeLog.push(2);
        } else if (op.charAt(0) == '3') {
            int k = Integer.parseInt(op.substring(2).trim());
            out.add(s.charAt(k - 1));
        } else {
            int t = typeLog.pop();
            if (t == 1) {
                int len = appendLog.pop()[0];
                s.delete(s.length() - len, s.length());
            } else {
                String removed = deleteLog.pop();
                s.append(removed);
            }
        }
    }
    return out;
}

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Snapshotting after the mutation

Undo must restore the state that existed BEFORE the change. If you push the snapshot after mutating, you save the post-change string and undo becomes a no-op.

Explore the code comparison

Don't write this

s.extend(w)
history.append(s.copy())   # too late: saved the AFTER state

Write this instead

history.append(s.copy())   # save BEFORE
s.extend(w)

Treating print/undo as undoable

Only append and delete change S. Pushing history on a print or on undo itself adds bogus entries, so a later undo reverts the wrong (or a non-existent) operation.

Explore the code comparison

Don't write this

// type 3 (print)
history.push(s.toString());   // wrong: print is read-only
out.add(s.charAt(k - 1));

Write this instead

// type 3 (print)
out.add(s.charAt(k - 1));     // no history change

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Stack of state snapshots for O(1) undo

Code pattern to memorize

append(W): history.push(S); S = S + W
delete(k): history.push(S); S = S[:-k]
print(k):  output S[k-1]
undo():    S = history.pop()

Rules to remember

1Push the current string onto the history stack before mutating it on append (type 1) and delete (type 2).
2Undo (type 4) just pops the stack and assigns it back to S — restoring the exact prior state.
3Print (type 3) and undo do not push history; only the two mutating ops do.
4Use 1-indexed access for print: the k-th character is S[k-1].
5Avoid re-copying the whole string per char-append — use StringBuilder (Java) / a list of segments, or accept that snapshotting strings is the simplest correct approach.

Use this pattern when

Editor-style undo where each undo reverts exactly one prior mutation
Any 'undo the last operation' requirement → snapshot or inverse-op stack
Versioned state where you only ever step backward one step at a time
Command pattern with reversible commands

Choose another pattern when

You also need redo → keep a second stack and move states between them
You need to jump to an arbitrary past version → persistent/immutable data structure or version list
Snapshots are huge and frequent → store inverse operations (what to undo) instead of full copies

Interview takeaway

Undo is a stack problem: snapshot the state before each reversible change, and undo pops back to it. The whole design is 'push before you mutate, pop to revert'. Storing inverse operations instead of full snapshots is the memory-optimised variant of the same idea.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternUndo via a stack: snapshot state (or store inverse operations) before each reversible mutation, pop to revert. Full snapshots are simplest; inverse-operation records are the memory-lean Command-pattern variant.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Add Redo
Coming soon
Keep a second stack; undo pushes the undone state onto the redo stack, redo pops it back.
Min Stack
Another auxiliary-stack design — track an aggregate alongside the main data.
Design Browser History
Coming soon
Back/forward is undo/redo over visited pages — two stacks or an index into a list.

Same pattern

←

Min Max Riddle

Continue · Next problem

Truck Tour

mediumStack QueueSometimes asked

Simple Text Editor

Stack & Queue · 14 of 17 · 9 min

Implement a simple text editor over an initially empty string S. Process q operations of four types:

1 W — append the string W to the end of S.
2 k — delete the last k characters of S.
3 k — print the k-th character of S (1-indexed).
4 — undo the last not-yet-undone append or delete, reverting S to its previous value.

Print the result of each type-3 operation on its own line.

In plain English

Examples

Example 1

Input: ops = ["1 abc", "3 3", "2 3", "1 xy", "3 2", "4", "4", "3 1"]
Output: c y a
Note: After '1 abc' S='abc' (print 3rd='c'). '2 3' → S=''. '1 xy' → S='xy' (print 2nd='y'). undo → S=''. undo → S='abc' (print 1st='a').

Example 2

Input: ops = ["1 abcde", "1 fg", "3 7", "4", "3 5"]
Output: g e
Note: S='abcde' then 'abcdefg' (7th='g'). undo reverts the second append → S='abcde' (5th='e').

Example 3

Input: ops = ["1 xy", "2 1", "3 1", "4", "3 2"]
Output: x y
Note: S='xy', delete 1 → 'x' (1st='x'). undo restores 'xy' (2nd='y').

Constraints

1 ≤ q ≤ 10⁶
1 ≤ k ≤ |S| for delete and print operations
Total length of all appended strings ≤ 10⁶
Every type-4 (undo) has a matching prior append or delete to revert
Operations should be efficient (amortised near O(1) per op, O(length) per append)

Clarifying questions4First question: Does undo revert exactly one operation, or everything?Explore questions

Q1.Does undo revert exactly one operation, or everything?
Exactly one — the most recent append or delete that hasn't been undone yet. That LIFO behaviour is why a stack fits.
Q2.Are print and undo themselves undoable?
No. Only append and delete mutate S and are undoable. Print is read-only, and undo is the mechanism, not a tracked operation.
Q3.Is the print index 1-based or 0-based?
1-based. The k-th character is at index k−1 in a 0-indexed string.
Q4.Could the snapshots be large? Any memory concern?
Storing full string copies is simplest but can be memory-heavy. The leaner option stores inverse operations: for an append, record 'remove the appended suffix'; for a delete, record the deleted suffix to re-append.

Stack & Queue

Progress14/17

DifficultyMedium

OptimalO(1) undo, O(|W|) append, O(1) delete · O(total characters) but only the deltas, not full snapshots

FrequencySometimes asked

Read9–11 min

Asked at

AmazonMicrosoftGoogleBloombergAdobe

In this module

PrevMin Max Riddle NextTruck Tour

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you model undo with a stack of prior states (or inverse operations) and correctly snapshot only on mutating operations, with clean 1-indexed access.

Where candidates slip

Pushing history on print/undo too (corrupting the undo chain), snapshotting AFTER the mutation, or using 0-indexed access for the 1-indexed print query.

How to stand out

State the 'push current state before mutating' invariant, note undo is O(1), and mention the memory-leaner alternative of storing inverse operations rather than full string copies.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Stack of Full State Snapshots (Clear and Correct)	`O(1) undo, O(\|W\|) append, O(1) delete (amortised)`	`O(total characters across snapshots)`	The straightforward, interview-safe answer. Note it's the simplest correct model and that snapshots can be memory-heavy.	Read
2	Stack of Inverse Operations (Memory-Optimised)Optimal	`O(1) undo, O(\|W\|) append, O(1) delete`	`O(total characters) but only the deltas, not full snapshots`	Bring up when memory matters at q = 10⁶: store how to reverse each op instead of full copies.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Stack of Full State Snapshots (Clear and Correct)

TimeO(1) undo, O(|W|) append, O(1) delete (amortised)SpaceO(total characters across snapshots)

The straightforward, interview-safe answer. Note it's the simplest correct model and that snapshots can be memory-heavy.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Undo reverts the most recent mutation. What data structure gives last-in-first-out access to past states?

2Hint 2Explore hint

Before each append or delete, push the current string onto a stack. Then mutate.

3Hint 3Explore hint

Undo pops the stack and assigns the popped state back to S. Print and undo never push.

A · Core idea

Keep S and a history stack of previous values of S.

Snapshot before mutating. On an append (1 W) or delete (2 k), first push the current S onto history, then perform the change. The snapshot captures the state to which undo must return.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

ops = ["1 abc", "3 3", "2 3", "1 xy", "3 2", "4", "4", "3 1"]

Array state

after 1 abc

S='abc', history=['']

[0]

Current pointerResolved stateNot processed

Final result

c
y
a

C · Code with teaching comments

solution.javaJava

Stack of Full State Snapshots (Clear and Correct) — reference

5 teaching notes

1
import java.util.*;
2
 
3
public List<Character> simpleTextEditor(String[] ops) {
4
    StringBuilder s = new StringBuilder();
5
    Deque<String> history = new ArrayDeque<>();
6
    List<Character> out = new ArrayList<>();
7
    for (String op : ops) {
8
        if (op.charAt(0) == '1') {
9
            String w = op.substring(2);
10
            // Snapshot the CURRENT state before appending — this is what undo restores.
11
            history.push(s.toString());
12
            // Append the new text after snapshotting.
13
            s.append(w);
14
        } else if (op.charAt(0) == '2') {
15
            int k = Integer.parseInt(op.substring(2).trim());
16
            history.push(s.toString());
17
            // Delete the last k characters (snapshot was already pushed).
18
            s.delete(s.length() - k, s.length());
19
        } else if (op.charAt(0) == '3') {
20
            int k = Integer.parseInt(op.substring(2).trim());
21
            // Print is 1-indexed → charAt(k-1); no history change.
22
            out.add(s.charAt(k - 1));
23
        } else {
24
            // Undo: restore the most recent snapshot. O(1) stack pop.
25
            s = new StringBuilder(history.pop());
26
        }
27
    }
28
    return out;
29
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.29 lines

D · Why it works and complexityO(1) undo, O(|W|) append, O(1) delete (amortised) timeO(total characters across snapshots) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6delete everything then undo — '2 k' with k = |S| pushes the full string and empties S; undo restores it fully.Explore edge cases

Edge cases handled

delete everything then undo'2 k' with k = |S| pushes the full string and empties S; undo restores it fully.
undo right after an appendPops the pre-append snapshot, removing exactly the appended text.

Pitfalls

Pushing a snapshot on print or undo — corrupts the undo chain.
Snapshotting AFTER mutating instead of before — undo then restores the wrong state.
0-indexing the print query — the k-th character is at index k−1.
Re-building S from a copied string per character append can be O(n²) — use StringBuilder/list.

03.2

Approach 2 of 2 · Optimal

Stack of Inverse Operations (Memory-Optimised)

TimeO(1) undo, O(|W|) append, O(1) deleteSpaceO(total characters) but only the deltas, not full snapshots

Bring up when memory matters at q = 10⁶: store how to reverse each op instead of full copies.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Instead of saving the whole string before each change, save just what's needed to reverse that one change.

2Hint 2Explore hint

To undo an append of W, you only need to chop |W| characters off the end. To undo a delete of the last k chars, you need those k characters back.

3Hint 3Explore hint

Push a small record per mutation: ('append', len) or ('delete', removedSubstring). Undo applies the inverse.

A · Core idea

Rather than snapshotting the entire string, record the inverse of each mutation so undo can replay it backward.

Delete inverse. When you delete the last k characters, undo must put them back. So before deleting, capture the removed suffix and push ('D', removedSuffix). Undo re-appends that suffix.

Same stack discipline. Push on mutate, pop on undo, never on print. Only the payload changes from 'whole state' to 'how to reverse this step'.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

ops = ["1 abcde", "1 fg", "3 7", "4", "3 5"]

Array state

after appends

S='abcdefg', history=[('A',5),('A',2)]

A:5

[0]

A:2

[1]

Current pointerResolved stateNot processed

Final result

g
e

C · Code with teaching comments

solution.javaJava

Stack of Inverse Operations (Memory-Optimised) — optimal

6 teaching notes

1
import java.util.*;
2
 
3
public List<Character> simpleTextEditor(String[] ops) {
4
    StringBuilder s = new StringBuilder();
5
    Deque<int[]> appendLog = new ArrayDeque<>();   // marker for append: {1, len}
6
    Deque<String> deleteLog = new ArrayDeque<>();   // removed suffixes
7
    Deque<Integer> typeLog = new ArrayDeque<>();    // 1 = append, 2 = delete
8
    List<Character> out = new ArrayList<>();
9
    for (String op : ops) {
10
        if (op.charAt(0) == '1') {
11
            String w = op.substring(2);
12
            s.append(w);
13
            // To undo an append, we only need to know how many chars to chop.
14
            appendLog.push(new int[]{w.length()});
15
            typeLog.push(1);
16
        } else if (op.charAt(0) == '2') {
17
            int k = Integer.parseInt(op.substring(2).trim());
18
            // Capture the suffix BEFORE deleting so undo can restore it.
19
            String removed = s.substring(s.length() - k);
20
            s.delete(s.length() - k, s.length());
21
            // Record the removed text as the delete's inverse payload.
22
            deleteLog.push(removed);
23
            typeLog.push(2);
24
        } else if (op.charAt(0) == '3') {
25
            int k = Integer.parseInt(op.substring(2).trim());
26
            out.add(s.charAt(k - 1));
27
        } else {
28
            // Undo: find out whether the last mutation was an append or delete.
29
            int t = typeLog.pop();
30
            if (t == 1) {
31
                int len = appendLog.pop()[0];
32
                // Undo append by removing the appended suffix.
33
                s.delete(s.length() - len, s.length());
34
            } else {
35
                String removed = deleteLog.pop();
36
                // Undo delete by re-appending the captured suffix.
37
                s.append(removed);
38
            }
39
        }
40
    }
41
    return out;
42
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.42 lines

D · Why it works and complexityO(1) undo, O(|W|) append, O(1) delete timeO(total characters) but only the deltas, not full snapshots spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls5undo an append of length |S| — Chops the entire appended block, returning S to its pre-append value.Explore edge cases

Edge cases handled

undo an append of length |S|Chops the entire appended block, returning S to its pre-append value.
undo a full deleteRe-appends the whole captured suffix, restoring S exactly.

Pitfalls

Capturing the deleted suffix AFTER deleting — it's already gone; capture before.
Forgetting to record the operation type, so undo can't tell append from delete.
Mismatched logs (separate stacks drifting) — a single stack of tagged records is safer.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

import java.util.*;

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Snapshotting after the mutation

Undo must restore the state that existed BEFORE the change. If you push the snapshot after mutating, you save the post-change string and undo becomes a no-op.

Explore the code comparison

Don't write this

s.extend(w)
history.append(s.copy())   # too late: saved the AFTER state

Write this instead

history.append(s.copy())   # save BEFORE
s.extend(w)

Treating print/undo as undoable

Only append and delete change S. Pushing history on a print or on undo itself adds bogus entries, so a later undo reverts the wrong (or a non-existent) operation.

Explore the code comparison

Don't write this

// type 3 (print)
history.push(s.toString());   // wrong: print is read-only
out.add(s.charAt(k - 1));

Write this instead

// type 3 (print)
out.add(s.charAt(k - 1));     // no history change

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Stack of state snapshots for O(1) undo

Code pattern to memorize

append(W): history.push(S); S = S + W
delete(k): history.push(S); S = S[:-k]
print(k):  output S[k-1]
undo():    S = history.pop()

Rules to remember

1Push the current string onto the history stack before mutating it on append (type 1) and delete (type 2).
2Undo (type 4) just pops the stack and assigns it back to S — restoring the exact prior state.
3Print (type 3) and undo do not push history; only the two mutating ops do.
4Use 1-indexed access for print: the k-th character is S[k-1].
5Avoid re-copying the whole string per char-append — use StringBuilder (Java) / a list of segments, or accept that snapshotting strings is the simplest correct approach.

Use this pattern when

Editor-style undo where each undo reverts exactly one prior mutation
Any 'undo the last operation' requirement → snapshot or inverse-op stack
Versioned state where you only ever step backward one step at a time
Command pattern with reversible commands

Choose another pattern when

You also need redo → keep a second stack and move states between them
You need to jump to an arbitrary past version → persistent/immutable data structure or version list
Snapshots are huge and frequent → store inverse operations (what to undo) instead of full copies

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Add Redo
Coming soon
Keep a second stack; undo pushes the undone state onto the redo stack, redo pops it back.
Min Stack
Another auxiliary-stack design — track an aggregate alongside the main data.
Design Browser History
Coming soon
Back/forward is undo/redo over visited pages — two stacks or an index into a list.

Same pattern

←

Min Max Riddle

Continue · Next problem

Truck Tour