2296. Design a Text Editor

Problem Description

The problem requires us to design a simple text editor with basic functionalities such as adding text, deleting text, and moving the cursor left or right. Unlike standard text editors that deal with complex rendering and formatting, our task is to simulate how the internal state of the text editor changes as these operations are performed. The editor will keep track of the cursor position and allow the following actions:

• Add text: Insert a given string of text where the cursor is currently positioned. After the text is added, the cursor should be at the end of the newly added text.
• Delete text: Remove a specified number of characters from the text, directly to the left of the cursor position. The function should return the actual number of characters deleted, which could be less than the requested if there are not enough characters.
• Move cursor left: Shift the cursor to the left 'k' positions. If there aren't 'k' characters to the left of the cursor, move the cursor as far as possible. After moving, the function should return a string containing the last 10 (or fewer, if less than 10 characters are available) characters to the left of the cursor.
• Move cursor right: Shift the cursor to the right 'k' positions. Similarly, this should also return the last 10 (or fewer) characters to the left of the text where the cursor is now placed after the movement.

The cursor is limited to the bounds of the current text content, meaning it cannot move further left than the first character or further right than the last character of the text.

Intuition

A straightforward approach to solve this problem is to use two stacks—a "left" stack to represent the text before the cursor and a "right" stack to represent the text after the cursor. This method leverages the properties of stacks to manage the characters efficiently in both directions relative to the cursor:

1. When we add text, we push the new characters to the "left" stack, as they are added where the cursor currently is, which is at the end of the existing text in the "left" stack.
2. When performing the delete operation, we pop characters from the "left" stack, simulating the deletion of characters to the left of the cursor.
3. To move the cursor to the left, we pop characters from the "left" stack and push them onto the "right" stack, effectively moving the cursor backwards. The last 10 characters of the "left" stack are then concatenated into a string and returned.
4. To move the cursor to the right, we pop characters from the "right" stack and push them onto the "left" stack, like 'undoing' a leftward cursor move. Again, we concatenate and return the last 10 characters of the "left" stack.

Through the push and pop operations of stacks, we can control the text before and after the cursor efficiently, and maintain an accurate picture of what the characters around the cursor would be after each operation.

Learn more about Stack and Linked List patterns.

Solution Approach

The solution approach for the text editor design involves using two stacks, referred to in the code as self.left and self.right, to hold characters on each side of the cursor. Here's a detailed explanation of how each method in the TextEditor class works:

• Constructor (__init__): Initializes two lists, self.left and self.right, which act as stacks. These stacks are empty at the start, representing an empty text state with the cursor at the initial position.

• Add text (addText): Takes a string text as input and extends the self.left stack with the new characters. This simulates typing at the cursor's position, as characters are appended where the cursor is. After adding, the cursor ends up to the right of the new text, naturally.

• Delete text (deleteText): Takes an integer k representing the number of characters to delete. The actual number of deletions cannot exceed the number of characters in self.left, so min(k, len(self.left)) is calculated to determine the true number of deletible characters. The method then pops these characters from the self.left stack and returns the count of the deleted characters. Each pop removes a character on the left of the cursor, mimicking a backspace operation.

• Move cursor left (cursorLeft): Transfers k characters from the self.left stack to the self.right stack, if available, moving the cursor left k times. If there are fewer than k characters, it moves the cursor to the start. It then returns a string composed of the last 10 (or fewer if less than 10 are available) characters of the self.left stack, reflecting the text immediately left of the cursor after the move.

• Move cursor right (cursorRight): Moves the cursor to the right by transferring k characters from the self.right stack back to the self.left stack, simulating a forward cursor movement. As with the left move, it only moves as far as characters exist in self.right. It then returns a string of up to the last 10 characters from the self.left stack.

These stack operations (push and pop) allow the text editor to efficiently mimic the addition, deletion, and cursor movement actions. Stacks are chosen due to their LIFO (last in, first out) nature, which perfectly suits the operations we need to simulate for this text editor design.

Example Walkthrough

Let's consider we are using the TextEditor class described above to perform a series of operations on our text editor. Suppose we start with an empty text field, and we want to perform the following actions:

1. Add text "hello".
2. Move cursor left by 2 positions.
3. Add text "X".
4. Delete text of 1 character.
5. Move cursor right by 1 position.

Here's how the TextEditor class handles these operations:

• Initial State: (Cursor at the start) left = [], right = []

• Add text "hello": The addText method appends each character of "hello" to self.left. left = ['h', 'e', 'l', 'l', 'o'], right = [] (Cursor is now at the end of "hello")

• Move cursor left by 2: The cursorLeft(2) method moves the cursor 2 positions to the left. It pops two characters from self.left and pushes them into self.right. left = ['h', 'e', 'l'], right = ['l', 'o'] Last 10 characters of the left stack: "hel"

• Add text "X": The addText method adds the "X" character to self.left. left = ['h', 'e', 'l', 'X'], right = ['l', 'o'] (Cursor is now after "X")

• Delete text of 1 character: The deleteText(1) method deletes 1 character from the left of the cursor by popping from self.left. left = ['h', 'e', 'l'], right = ['l', 'o'] 1 character was deleted.

• Move cursor right by 1: The cursorRight(1) method moves the cursor 1 position to the right. It pops one character from self.right and pushes it into self.left. left = ['h', 'e', 'l', 'l'], right = ['o'] Last 10 characters of the left stack: "hell"

After all these operations, the state of the text editor and stacks are as follows:
Text Content: "hell|o" (with the cursor positioned at "|")
left = ['h', 'e', 'l', 'l']
right = ['o']

Each of these operations efficiently alters the state of the text editor by using the two-stack approach while keeping track of the cursor's position, as described in the solution approach.

Solution Implementation

Time and Space Complexity

Time Complexity

1. addText(text: str) -> None:

   • Appending each character from the input text to the self.left list has a time complexity of O(n) where n is the length of text.

2. deleteText(k: int) -> int:

   • Deleting k elements from the end of self.left list has a time complexity of O(k) since each pop operation is O(1) and k such operations are performed.

3. cursorLeft(k: int) -> str:

   • Moving cursor left k times involves popping elements from self.left and appending to self.right, each operation takes O(1) so overall operation is O(k). Then, joining the last 10 characters of self.left is O(1), as it deals with at most 10 characters regardless of the input size.

4. cursorRight(k: int) -> str:

   • Similar to cursorLeft, moving the cursor right has a time complexity of O(k) for moving characters, and O(1) for joining up to 10 characters. So, overall complexity is O(k).

Space Complexity

• The overall space complexity of the TextEditor class is O(m + n) where m is the total number of characters to the left of cursor and n is the total number of characters to the right of cursor. Since the input text is stored within these two lists, this accounts for the space taken up by the editor's content.

Learn more about how to find time and space complexity quickly using problem constraints.