LeetCode 2296 - Design a Text Editor

LeetCode Problem 2296

Difficulty: 🔴 Hard
Topics: Linked List, String, Stack, Design, Simulation, Doubly-Linked List

Solution

Problem Understanding

This problem asks us to design a simplified text editor that supports four operations:

1. Inserting text at the current cursor position
2. Deleting characters to the left of the cursor
3. Moving the cursor left
4. Moving the cursor right

The cursor behaves exactly like a cursor in a normal text editor. It always sits between characters, and its position must remain within the valid range of the text.

For example:

• "abc|" means the cursor is at the end
• "|abc" means the cursor is at the beginning
• "ab|cd" means the cursor is between b and c

The important detail is that all editing operations happen relative to the cursor.

The addText(text) operation inserts the given string at the cursor position and then moves the cursor to the end of the inserted text.

The deleteText(k) operation simulates pressing backspace up to k times. Only characters to the left of the cursor can be deleted. The function returns how many characters were actually removed.

The cursorLeft(k) operation moves the cursor left by at most k positions. If the cursor reaches the beginning of the text, it stops there. After moving, we must return the last up to 10 characters that exist to the left of the cursor.

The cursorRight(k) operation behaves similarly, except the cursor moves to the right.

The constraints are relatively small:

• Each inserted string has length at most 40
• Each movement or deletion parameter is at most 40
• At most 2 * 10^4 operations occur

Although the constraints are not massive, the problem explicitly asks for an O(k) per operation solution in the follow-up. This strongly suggests we should avoid rebuilding the entire string repeatedly.

Several edge cases are important:

• Deleting more characters than exist to the left of the cursor
• Moving the cursor beyond the beginning
• Moving the cursor beyond the end
• Returning fewer than 10 characters when the left side is short
• Operating on an initially empty editor

A naive implementation using repeated string slicing may work under these constraints, but it is inefficient conceptually and does not satisfy the intended follow-up complexity.

Approaches

Brute Force Approach

The most direct solution is to store the entire text as a single string and maintain an integer cursor index.

For insertion:

• Split the string into left and right parts around the cursor
• Insert the new text in the middle
• Rebuild the entire string

For deletion:

• Remove up to k characters before the cursor
• Rebuild the string again

For cursor movement:

• Update the cursor index
• Extract the last 10 characters from the left side

This approach is easy to understand and implement. Every operation directly manipulates the actual text representation.

However, strings are immutable in Python and Go. Rebuilding strings repeatedly causes large copying overhead. If the text becomes large, every insertion and deletion may require copying the entire string.

Although the given constraints are small enough for this to pass, it does not meet the intended follow-up complexity.

Optimal Approach

The key observation is that the cursor naturally divides the text into two halves:

• Characters to the left of the cursor
• Characters to the right of the cursor

Instead of storing one large string, we can maintain two stacks:

• left, containing characters left of the cursor
• right, containing characters right of the cursor

The cursor conceptually sits between these two stacks.

For example:

left = ['a', 'b', 'c']
right = ['f', 'e', 'd']

represents:

abc|def

Notice that the right stack is stored in reverse order so we can efficiently move characters between stacks.

This design makes every operation local:

• Insertions append to left
• Deletions pop from left
• Moving left transfers characters from left to right
• Moving right transfers characters from right to left

Each operation only touches the affected characters, which gives O(k) complexity.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n) per operation	O(n)	Rebuilds entire string repeatedly
Optimal	O(k) per operation	O(n)	Uses two stacks around the cursor

Algorithm Walkthrough

Data Structure Design

We maintain two stacks:

• left, characters before the cursor
• right, characters after the cursor, stored in reverse order

The cursor always exists between them.

If:

left = ['l', 'e', 'e', 't']
right = ['e', 'd', 'o', 'c']

then the actual text is:

leet|code

Step-by-Step Algorithm

1. Initialize two empty stacks.

The editor starts with no text, so both sides of the cursor are empty. 2. Handle addText(text).

For every character in text, append it to left.

This works because inserted text always appears immediately before the cursor, and after insertion the cursor moves to the end of the new text. 3. Handle deleteText(k).

Repeatedly pop characters from left until either:

• k characters are deleted
• left becomes empty

Count how many characters were actually removed and return that value. 4. Handle cursorLeft(k).

Move the cursor left by transferring characters from left to right.

Each move:

• pops one character from left
• pushes it onto right

Stop if either:

• k moves are completed
• left becomes empty

5. Handle cursorRight(k).

Move the cursor right by transferring characters from right to left.

Each move:

• pops one character from right
• pushes it onto left

Stop if either:

• k moves are completed
• right becomes empty

6. Return the last 10 characters left of the cursor.

Since left stores all characters before the cursor in correct order, the answer is simply:

''.join(left[-10:])

Why it works

The invariant is that:

• left always contains exactly the characters before the cursor
• right always contains exactly the characters after the cursor, in reverse order

Every operation preserves this invariant:

• Insertions only extend the left side
• Deletions only remove from the left side
• Cursor movement transfers characters between sides without changing text order

Because the invariant always holds, the editor state remains correct after every operation.

Python Solution

class TextEditor:

    def __init__(self):
        self.left = []
        self.right = []

    def addText(self, text: str) -> None:
        for ch in text:
            self.left.append(ch)

    def deleteText(self, k: int) -> int:
        deleted = 0

        while self.left and deleted < k:
            self.left.pop()
            deleted += 1

        return deleted

    def cursorLeft(self, k: int) -> str:
        moves = 0

        while self.left and moves < k:
            self.right.append(self.left.pop())
            moves += 1

        return ''.join(self.left[-10:])

    def cursorRight(self, k: int) -> str:
        moves = 0

        while self.right and moves < k:
            self.left.append(self.right.pop())
            moves += 1

        return ''.join(self.left[-10:])

The implementation directly follows the two-stack design.

The constructor initializes two empty lists that behave as stacks.

The addText method appends characters to left, because inserted text appears immediately before the cursor.

The deleteText method repeatedly pops from left. This naturally deletes characters to the left of the cursor exactly like backspace behavior.

The cursor movement methods transfer characters between the two stacks. Moving left removes a character from the left side and places it on the right side. Moving right performs the reverse operation.

Finally, both movement methods return the last up to 10 characters from left, since left always stores the exact text before the cursor.

Go Solution

type TextEditor struct {
	left  []byte
	right []byte
}

func Constructor() TextEditor {
	return TextEditor{
		left:  []byte{},
		right: []byte{},
	}
}

func (this *TextEditor) AddText(text string) {
	for i := 0; i < len(text); i++ {
		this.left = append(this.left, text[i])
	}
}

func (this *TextEditor) DeleteText(k int) int {
	deleted := 0

	for len(this.left) > 0 && deleted < k {
		this.left = this.left[:len(this.left)-1]
		deleted++
	}

	return deleted
}

func (this *TextEditor) CursorLeft(k int) string {
	moves := 0

	for len(this.left) > 0 && moves < k {
		ch := this.left[len(this.left)-1]
		this.left = this.left[:len(this.left)-1]
		this.right = append(this.right, ch)
		moves++
	}

	start := 0
	if len(this.left) > 10 {
		start = len(this.left) - 10
	}

	return string(this.left[start:])
}

func (this *TextEditor) CursorRight(k int) string {
	moves := 0

	for len(this.right) > 0 && moves < k {
		ch := this.right[len(this.right)-1]
		this.right = this.right[:len(this.right)-1]
		this.left = append(this.left, ch)
		moves++
	}

	start := 0
	if len(this.left) > 10 {
		start = len(this.left) - 10
	}

	return string(this.left[start:])
}

The Go implementation mirrors the Python logic closely.

Instead of Python lists, Go uses []byte slices as stacks. Since the input only contains lowercase English letters, bytes are sufficient and more efficient than rune slices.

Appending and removing from the end of slices gives efficient stack behavior.

The substring extraction is handled by slicing left[start:] and converting it into a string.

Go does not require any special handling for integer overflow here because all constraints are small.

Worked Examples

Example 1

Operations:

addText("leetcode")
deleteText(4)
addText("practice")
cursorRight(3)
cursorLeft(8)
deleteText(10)
cursorLeft(2)
cursorRight(6)

Operation	Left Stack	Right Stack	Visible Text
Start	[]	[]	|
addText("leetcode")	leetcode	[]	leetcode|
deleteText(4)	leet	[]	leet|
addText("practice")	leetpractice	[]	leetpractice|
cursorRight(3)	leetpractice	[]	leetpractice|
cursorLeft(8)	leet	ecitcarp	leet|practice
deleteText(10)	[]	ecitcarp	|practice
cursorLeft(2)	[]	ecitcarp	|practice
cursorRight(6)	practi	ec	practi|ce

Returned values:

Operation	Return Value
deleteText(4)	4
cursorRight(3)	"etpractice"
cursorLeft(8)	"leet"
deleteText(10)	4
cursorLeft(2)	""
cursorRight(6)	"practi"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(k) per operation	Each operation moves, inserts, or deletes at most k characters
Space	O(n)	All characters are stored exactly once across the two stacks

The important observation is that every operation only manipulates the directly affected characters. We never rebuild the entire text string. Because each cursor movement or deletion processes at most k characters, every operation runs in linear time relative to the requested amount of work.

The total space usage is linear in the total text size because every character exists in exactly one of the two stacks.

Test Cases

# Provided example
editor = TextEditor()
editor.addText("leetcode")
assert editor.deleteText(4) == 4  # delete existing chars
editor.addText("practice")
assert editor.cursorRight(3) == "etpractice"  # cannot move beyond end
assert editor.cursorLeft(8) == "leet"  # move left normally
assert editor.deleteText(10) == 4  # delete fewer than requested
assert editor.cursorLeft(2) == ""  # already at beginning
assert editor.cursorRight(6) == "practi"  # move right normally

# Empty editor operations
editor = TextEditor()
assert editor.deleteText(5) == 0  # delete from empty editor
assert editor.cursorLeft(3) == ""  # move left on empty text
assert editor.cursorRight(3) == ""  # move right on empty text

# Simple insertion
editor = TextEditor()
editor.addText("abc")
assert editor.cursorLeft(0) == "abc"  # no movement

# Cursor movement boundaries
editor = TextEditor()
editor.addText("abcdef")
assert editor.cursorLeft(100) == ""  # move beyond beginning
assert editor.cursorRight(100) == "abcdef"  # move beyond end

# Delete exact amount
editor = TextEditor()
editor.addText("hello")
assert editor.deleteText(5) == 5  # delete all characters
assert editor.cursorLeft(1) == ""  # editor now empty

# Interleaved operations
editor = TextEditor()
editor.addText("abc")
editor.cursorLeft(1)
editor.addText("X")
assert editor.cursorRight(1) == "abXc"  # insertion in middle

# Return only last 10 characters
editor = TextEditor()
editor.addText("abcdefghijklmnop")
assert editor.cursorLeft(0) == "ghijklmnop"  # only last 10 chars

# Multiple cursor moves
editor = TextEditor()
editor.addText("abcdef")
assert editor.cursorLeft(2) == "abcd"  # partial left move
assert editor.cursorRight(1) == "abcde"  # partial right move

Test	Why
Provided example	Validates all required operations together
Empty editor operations	Ensures safe handling of empty state
Simple insertion	Verifies insertion and no-op cursor movement
Cursor movement boundaries	Ensures cursor never leaves valid range
Delete exact amount	Tests full deletion behavior
Interleaved operations	Validates insertion in the middle of text
Return only last 10 characters	Confirms output truncation rule
Multiple cursor moves	Verifies stack transfer correctness

Edge Cases

One important edge case occurs when deleting more characters than exist to the left of the cursor. A buggy implementation might attempt to remove nonexistent characters and crash. Our implementation avoids this by stopping deletion once the left stack becomes empty. The returned value accurately reflects how many characters were actually deleted.

Another important case happens when moving the cursor beyond the text boundaries. For example, calling cursorLeft(100) when only 3 characters exist to the left. The algorithm safely stops movement once no more characters are available. The same logic applies symmetrically for cursorRight.

A subtle edge case involves returning the last 10 characters to the left of the cursor. If fewer than 10 characters exist, we must return only the available characters. The slicing operation left[-10:] naturally handles this correctly in Python, and the Go implementation computes a safe starting index before slicing.

A final important case occurs when inserting text in the middle of existing content. The two-stack structure handles this naturally because the cursor position is represented by the split between the stacks. Newly inserted characters are simply appended to left, which places them exactly at the cursor position without rebuilding the entire text.