LeetCode Solutions Blog

Design a Text Editor

Number: 2389

Difficulty: Hard

Paid? No

Problem Description

Design a text editor with a movable cursor that supports adding text, deleting text (like the backspace key), and moving the cursor left or right. Deletion only removes characters to the left of the cursor, and the cursor cannot move out of the bounds of the current text.

Key Insights

Use two separate data structures (stacks) to represent the text to the left and right of the cursor.
The left stack holds characters before the cursor, while the right stack holds characters after the cursor.
Each operation is executed in O(k) time where k is the number of characters to process in that operation.
Cursor movement is simulated by transferring characters between the left and right stacks.
For retrieving the last min(10, len) characters left of the cursor, simply extract from the left stack.

Space and Time Complexity

Time Complexity: O(k) per call for addText, deleteText, cursorLeft, and cursorRight where k is the number of characters processed. Space Complexity: O(n) overall, where n is the total number of characters maintained in both stacks.

Solution

We simulate a text editor using two stacks. One stack, leftStack, contains characters to the left of the cursor; the other, rightStack, contains characters to the right. When adding text, push characters onto leftStack. For deleting text, pop characters from leftStack. Moving the cursor left pops characters from leftStack into rightStack (up to k times or until leftStack is empty), and moving right pops from rightStack back into leftStack. After each cursor move, the solution returns the last 10 characters from leftStack (or whatever is available). This approach guarantees that each operation processes only the relevant k characters.

Code Solutions

Below are code solutions in multiple languages.

class TextEditor:
    def __init__(self):
        # left_stack contains text left to the cursor; right_stack contains text right to the cursor.
        self.left_stack = []
        self.right_stack = []
    
    def addText(self, text: str) -> None:
        # Append each character to left_stack.
        for ch in text:
            self.left_stack.append(ch)
    
    def deleteText(self, k: int) -> int:
        # Remove up to k characters from the left_stack.
        count = 0
        while self.left_stack and count < k:
            self.left_stack.pop()
            count += 1
        return count
    
    def cursorLeft(self, k: int) -> str:
        # Move at most k characters from left_stack to right_stack.
        count = 0
        while self.left_stack and count < k:
            self.right_stack.append(self.left_stack.pop())
            count += 1
        # Get last min(10, len(left_stack)) characters and return them as a string.
        return "".join(self.left_stack[-10:])
    
    def cursorRight(self, k: int) -> str:
        # Move at most k characters from right_stack back into left_stack.
        count = 0
        while self.right_stack and count < k:
            self.left_stack.append(self.right_stack.pop())
            count += 1
        # Get last min(10, len(left_stack)) characters and return them as a string.
        return "".join(self.left_stack[-10:])

# Example usage:
# textEditor = TextEditor()
# textEditor.addText("leetcode")
# print(textEditor.deleteText(4))
# textEditor.addText("practice")
# print(textEditor.cursorRight(3))
# print(textEditor.cursorLeft(8))
# print(textEditor.deleteText(10))
# print(textEditor.cursorLeft(2))
# print(textEditor.cursorRight(6))