# Design a Text Editor
**Difficulty:** HARD
[External](https://leetcode.com/problems/design-a-text-editor)
Canonical: https://scaleengineer.com/dsa/problems/design-a-text-editor
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design)
**Data structures:** Linked List, String, Stack, Doubly-Linked List
**Companies:** [Dropbox](https://scaleengineer.com/companies/dropbox), [Salesforce](https://scaleengineer.com/companies/salesforce), [Snap](https://scaleengineer.com/companies/snap), [Jane Street](https://scaleengineer.com/companies/jane-street), [Rubrik](https://scaleengineer.com/companies/rubrik), [Block](https://scaleengineer.com/companies/block), [Shopify](https://scaleengineer.com/companies/shopify)
---
## Problem
Design a text editor with a cursor that can do the following:

* **Add** text to where the cursor is.
* **Delete** text from where the cursor is (simulating the backspace key).
* **Move** the cursor either left or right.

When deleting text, only characters to the left of the cursor will be deleted. The cursor will also remain within the actual text and cannot be moved beyond it. More formally, we have that `0 <= cursor.position <= currentText.length` always holds.

Implement the `TextEditor` class:

* `TextEditor()` Initializes the object with empty text.
* `void addText(string text)` Appends `text` to where the cursor is. The cursor ends to the right of `text`.
* `int deleteText(int k)` Deletes `k` characters to the left of the cursor. Returns the number of characters actually deleted.
* `string cursorLeft(int k)` Moves the cursor to the left `k` times. Returns the last `min(10, len)` characters to the left of the cursor, where `len` is the number of characters to the left of the cursor.
* `string cursorRight(int k)` Moves the cursor to the right `k` times. Returns the last `min(10, len)` characters to the left of the cursor, where `len` is the number of characters to the left of the cursor.

**Example 1:**

**Input**
["TextEditor", "addText", "deleteText", "addText", "cursorRight", "cursorLeft", "deleteText", "cursorLeft", "cursorRight"]
[[], ["leetcode"], [4], ["practice"], [3], [8], [10], [2], [6]]
**Output**
[null, null, 4, null, "etpractice", "leet", 4, "", "practi"]

**Explanation**
TextEditor textEditor = new TextEditor(); // The current text is "|". (The '|' character represents the cursor)
textEditor.addText("leetcode"); // The current text is "leetcode|".
textEditor.deleteText(4); // return 4
                          // The current text is "leet|". 
                          // 4 characters were deleted.
textEditor.addText("practice"); // The current text is "leetpractice|". 
textEditor.cursorRight(3); // return "etpractice"
                           // The current text is "leetpractice|". 
                           // The cursor cannot be moved beyond the actual text and thus did not move.
                           // "etpractice" is the last 10 characters to the left of the cursor.
textEditor.cursorLeft(8); // return "leet"
                          // The current text is "leet|practice".
                          // "leet" is the last min(10, 4) = 4 characters to the left of the cursor.
textEditor.deleteText(10); // return 4
                           // The current text is "|practice".
                           // Only 4 characters were deleted.
textEditor.cursorLeft(2); // return ""
                          // The current text is "|practice".
                          // The cursor cannot be moved beyond the actual text and thus did not move. 
                          // "" is the last min(10, 0) = 0 characters to the left of the cursor.
textEditor.cursorRight(6); // return "practi"
                           // The current text is "practi|ce".
                           // "practi" is the last min(10, 6) = 6 characters to the left of the cursor.

**Constraints:**

* `1 <= text.length, k <= 40`
* `text` consists of lowercase English letters.
* At most `2 * 104` calls **in total** will be made to `addText`, `deleteText`, `cursorLeft` and `cursorRight`.

**Follow-up:** Could you find a solution with time complexity of `O(k)` per call?

# Approaches
## Brute Force with Single StringBuilder
This approach uses a single `StringBuilder` to store the entire text and an integer variable to maintain the cursor's position. While simple to conceptualize, operations like adding or deleting text in the middle are inefficient because they require shifting all subsequent characters.
**Time:** O(N) for `addText` and `deleteText`, where N is the current length of the text. `cursorLeft` and `cursorRight` are O(1) (as substring extraction is on at most 10 chars). Due to the O(N) operations, this approach is too slow for the given constraints. · **Space:** O(N), where N is the total number of characters in the text editor, to store the text in the `StringBuilder`.
**Pros:** Simple to understand and implement.; Uses standard, well-known Java library features.
**Cons:** The `addText` and `deleteText` operations are very slow (`O(N)`) for a large text body, as they require shifting a potentially large number of characters. This will lead to a Time Limit Exceeded error given the problem's constraints.
### Explanation
In this straightforward approach, we model the text editor's content with a `java.lang.StringBuilder` and the cursor's position with an integer index. 

- **Data Structures**: A `StringBuilder sb` holds the entire text, and an `int cursor` marks the insertion point (i.e., new text is inserted at `sb[cursor]`).
- **`addText(text)`**: We call `sb.insert(cursor, text)`. This method inserts the given `text` at the `cursor`'s position. However, this is costly because all characters from the cursor position to the end of the string must be shifted to the right. The cursor position is then advanced by the length of the added text.
- **`deleteText(k)`**: We delete `k` characters to the left of the cursor by calling `sb.delete(Math.max(0, cursor - k), cursor)`. Similar to insertion, this can be slow as it may require shifting all characters that were to the right of the deleted segment.
- **`cursorLeft(k)` / `cursorRight(k)`**: These are simple arithmetic operations on the `cursor` index, bounded by `0` and the current length of the text. They are very fast.
- **Returning Left Substring**: After a cursor move, we extract the last `min(10, cursor)` characters to the left of the cursor using `sb.substring()`. This is a fast operation as the length is small and fixed.

```java
class TextEditor {
    StringBuilder sb;
    int cursor;

    public TextEditor() {
        sb = new StringBuilder();
        cursor = 0;
    }

    public void addText(String text) {
        sb.insert(cursor, text);
        cursor += text.length();
    }

    public int deleteText(int k) {
        int start = Math.max(0, cursor - k);
        int end = cursor;
        if (start == end) return 0;
        int deletedCount = end - start;
        sb.delete(start, end);
        cursor = start;
        return deletedCount;
    }

    private String getLeftText() {
        int start = Math.max(0, cursor - 10);
        return sb.substring(start, cursor);
    }

    public String cursorLeft(int k) {
        cursor = Math.max(0, cursor - k);
        return getLeftText();
    }

    public String cursorRight(int k) {
        cursor = Math.min(sb.length(), cursor + k);
        return getLeftText();
    }
}
```
### Algorithm
- Initialize a `StringBuilder` `sb` to store the text and an integer `cursor` to track the cursor's position.
- `addText(text)`: Use `sb.insert(cursor, text)` to add text. This operation shifts all subsequent characters, taking `O(N)` time where `N` is the total text length.
- `deleteText(k)`: Use `sb.delete(cursor - k, cursor)` to remove text. This also takes `O(N)` time due to character shifting.
- `cursorLeft(k)` and `cursorRight(k)`: Update the `cursor` index. This is an `O(1)` operation. The required substring is then extracted, which takes constant time (`O(10)`).

## Doubly Linked List of Characters
To overcome the inefficiency of shifting elements in an array-based structure, this approach represents the text using a doubly linked list of characters. The cursor is a pointer to a node in the list. This structure allows for efficient `O(1)` insertions and deletions at any point in the list, once the position is located.
**Time:** `addText(text)` is O(L) where L is `text.length()`. `deleteText(k)`, `cursorLeft(k)`, and `cursorRight(k)` are all O(k). This is highly efficient. · **Space:** O(N), where N is the total number of characters. The constant factor is high due to storing two pointers for each character node.
**Pros:** All operations are efficient, with time complexities proportional to `k` or the length of the text being added (`L`), not the total text length `N`.; Satisfies the follow-up requirement of `O(k)` per call.
**Cons:** High memory overhead. Each character requires a `Node` object, which includes two pointers in addition to the character data. This can consume significantly more memory than a simple character array.; Implementation is more complex and error-prone compared to using a `StringBuilder`.
### Explanation
This approach models the text as a chain of character nodes, where each node is connected to its predecessor and successor. This allows for modifications in the middle of the text without affecting distant characters.

- **Data Structures**: We use a `Node` class with `char data`, `Node prev`, and `Node next`. The editor maintains a pointer, `cursor`, which points to the node just after the insertion point. Sentinel `head` and `tail` nodes are used to simplify list manipulation, especially for an empty list or when the cursor is at the beginning or end.
- **`addText(text)`**: We iterate through the input `text`. For each character, we create a new `Node` and insert it between `cursor.prev` and `cursor`. This involves updating four pointers and takes constant time per character.
- **`deleteText(k)`**: We perform `k` deletions. In each step, we identify the node to be deleted (`cursor.prev`), and then bypass it by linking its predecessor (`cursor.prev.prev`) to its successor (`cursor`). This is a constant time operation per character deletion.
- **`cursorLeft(k)` / `cursorRight(k)`**: Moving the cursor is achieved by simply traversing the list. To move left, we update `cursor = cursor.prev` `k` times. To move right, `cursor = cursor.next` `k` times.
- **Returning Left Substring**: We traverse backwards from `cursor.prev` for up to 10 nodes, appending each character to a `StringBuilder`, which is then reversed to get the correct order.

```java
class TextEditor {
    class Node {
        char c;
        Node prev, next;
        Node(char c) { this.c = c; }
    }

    Node cursor; // Node to the right of the conceptual cursor
    Node head, tail; // Sentinel nodes

    public TextEditor() {
        head = new Node(' ');
        tail = new Node(' ');
        head.next = tail;
        tail.prev = head;
        cursor = tail;
    }

    public void addText(String text) {
        for (char ch : text.toCharArray()) {
            Node newNode = new Node(ch);
            Node prevNode = cursor.prev;
            prevNode.next = newNode;
            newNode.prev = prevNode;
            newNode.next = cursor;
            cursor.prev = newNode;
        }
    }

    public int deleteText(int k) {
        int count = 0;
        for (int i = 0; i < k && cursor.prev != head; i++) {
            Node toDelete = cursor.prev;
            toDelete.prev.next = cursor;
            cursor.prev = toDelete.prev;
            count++;
        }
        return count;
    }

    private String getLeftText() {
        StringBuilder sb = new StringBuilder();
        Node curr = cursor.prev;
        for (int i = 0; i < 10 && curr != head; i++) {
            sb.append(curr.c);
            curr = curr.prev;
        }
        return sb.reverse().toString();
    }

    public String cursorLeft(int k) {
        for (int i = 0; i < k && cursor.prev != head; i++) {
            cursor = cursor.prev;
        }
        return getLeftText();
    }

    public String cursorRight(int k) {
        for (int i = 0; i < k && cursor != tail; i++) {
            cursor = cursor.next;
        }
        return getLeftText();
    }
}
```
### Algorithm
- Define a `Node` class for a doubly linked list, containing a character and `prev`/`next` pointers.
- Use two sentinel nodes, `head` and `tail`, to handle edge cases gracefully.
- The `cursor` is a pointer to the `Node` that is immediately to the right of the conceptual cursor.
- `addText(text)`: For each character in `text`, create a new `Node` and insert it before the `cursor` node by adjusting pointers. This is `O(1)` per character.
- `deleteText(k)`: For `k` times, remove the node to the left of the `cursor` (`cursor.prev`) by updating its neighbors' pointers. This is `O(1)` per deletion.
- `cursorLeft(k)` / `cursorRight(k)`: Move the `cursor` pointer `k` steps by following `prev` or `next` links.
- To get the text for return, traverse backwards from `cursor.prev` for up to 10 nodes.

## Two Stacks (Gap Buffer Simulation)
This is a highly efficient and practical approach that simulates a gap buffer using two stacks, which can be implemented conveniently with two `StringBuilder`s. The text is conceptually split at the cursor into a "left" part and a "right" part. By storing the right part in reverse, all operations at the cursor become manipulations at the end of the strings, which is very fast.
**Time:** `addText(text)` is O(L) where L is `text.length()`. `deleteText(k)`, `cursorLeft(k)`, and `cursorRight(k)` are all O(k). This is because all modifications happen at the end of the `StringBuilder`s, which is an amortized O(1) operation per character. · **Space:** O(N), where N is the total number of characters in the text. The space overhead is minimal.
**Pros:** Optimal time complexity for all operations, meeting the `O(k)` follow-up requirement.; More space-efficient than a character-based linked list.; Relatively straightforward to implement using standard library data structures.
**Cons:** The concept of storing the right part of the text in reverse order can be slightly counter-intuitive at first glance.
### Explanation
This optimal approach, often called the "two-stack" method, provides excellent performance by avoiding costly data shifts. It's a practical implementation of the gap buffer concept.

- **Data Structures**: We use two `StringBuilder`s, `left` and `right`. `left` stores the text to the left of the cursor in its natural order. `right` stores the text to the right of the cursor, but in *reverse* order. For example, if the text is `leet|practice`, then `left` = `"leet"` and `right` = `"ecitcarp"`.
- **`addText(text)`**: New text is always added at the cursor, so we simply append it to the `left` `StringBuilder`. This is an amortized `O(1)` operation per character.
- **`deleteText(k)`**: Deleting text to the left of the cursor means removing characters from the end of the `left` `StringBuilder`. This is done efficiently by shortening its length.
- **`cursorLeft(k)`**: To move the cursor left by `k` positions, we pop `k` characters from the end of `left` and append them to the end of `right`.
- **`cursorRight(k)`**: To move the cursor right by `k` positions, we pop `k` characters from the end of `right` (which are the characters immediately to the right of the cursor, but in reverse) and append them to `left`.
- **Returning Left Substring**: The required text is simply the last `min(10, left.length())` characters of the `left` `StringBuilder`.

This design ensures all operations manipulate the ends of the `StringBuilder`s, leveraging their amortized constant-time performance for append and delete-at-end operations.

```java
class TextEditor {
    StringBuilder left;  // Text to the left of the cursor
    StringBuilder right; // Text to the right of the cursor, in reverse order

    public TextEditor() {
        left = new StringBuilder();
        right = new StringBuilder();
    }

    public void addText(String text) {
        left.append(text);
    }

    public int deleteText(int k) {
        int actualDeleted = Math.min(k, left.length());
        left.setLength(left.length() - actualDeleted);
        return actualDeleted;
    }

    private String getLeftText() {
        int len = left.length();
        return left.substring(Math.max(0, len - 10));
    }

    public String cursorLeft(int k) {
        int count = Math.min(k, left.length());
        for (int i = 0; i < count; i++) {
            right.append(left.charAt(left.length() - 1));
            left.deleteCharAt(left.length() - 1);
        }
        return getLeftText();
    }

    public String cursorRight(int k) {
        int count = Math.min(k, right.length());
        for (int i = 0; i < count; i++) {
            left.append(right.charAt(right.length() - 1));
            right.deleteCharAt(right.length() - 1);
        }
        return getLeftText();
    }
}
```
### Algorithm
- Use two `StringBuilder`s: `left` for text before the cursor, and `right` for text after the cursor.
- Crucially, store the `right` part in reverse order. This makes operations at the cursor point (end of `left`, end of `right`) very fast.
- `addText(text)`: Append `text` to the `left` `StringBuilder`.
- `deleteText(k)`: Remove the last `k` characters from the `left` `StringBuilder`.
- `cursorLeft(k)`: Move `k` characters from the end of `left` to the end of `right`.
- `cursorRight(k)`: Move `k` characters from the end of `right` to the end of `left`.
- To get the text for return, take the last `min(10, left.length())` characters from `left`.

# Solutions
### Java

```java
class TextEditor { private StringBuilder left = new StringBuilder (); private StringBuilder right = new StringBuilder (); public TextEditor () { } public void addText ( String text ) { left . append ( text ); } public int deleteText ( int k ) { k = Math . min ( k , left . length ()); left . setLength ( left . length () - k ); return k ; } public String cursorLeft ( int k ) { k = Math . min ( k , left . length ()); for ( int i = 0 ; i < k ; ++ i ) { right . append ( left . charAt ( left . length () - 1 )); left . deleteCharAt ( left . length () - 1 ); } return left . substring ( Math . max ( left . length () - 10 , 0 )); } public String cursorRight ( int k ) { k = Math . min ( k , right . length ()); for ( int i = 0 ; i < k ; ++ i ) { left . append ( right . charAt ( right . length () - 1 )); right . deleteCharAt ( right . length () - 1 ); } return left . substring ( Math . max ( left . length () - 10 , 0 )); } } /** * Your TextEditor object will be instantiated and called as such: * TextEditor obj = new TextEditor(); * obj.addText(text); * int param_2 = obj.deleteText(k); * String param_3 = obj.cursorLeft(k); * String param_4 = obj.cursorRight(k); */
```

### CPP

```cpp
class TextEditor { public: TextEditor () { } void addText ( string text ) { left += text ; } int deleteText ( int k ) { k = min ( k , ( int ) left . size ()); left . resize ( left . size () - k ); return k ; } string cursorLeft ( int k ) { k = min ( k , ( int ) left . size ()); while ( k -- ) { right += left . back (); left . pop_back (); } return left . substr ( max ( 0 , ( int ) left . size () - 10 )); } string cursorRight ( int k ) { k = min ( k , ( int ) right . size ()); while ( k -- ) { left += right . back (); right . pop_back (); } return left . substr ( max ( 0 , ( int ) left . size () - 10 )); } private: string left , right ; }; /** * Your TextEditor object will be instantiated and called as such: * TextEditor* obj = new TextEditor(); * obj->addText(text); * int param_2 = obj->deleteText(k); * string param_3 = obj->cursorLeft(k); * string param_4 = obj->cursorRight(k); */
```

### Python

```python
class TextEditor : def __init__ ( self ): self . left = [] self . right = [] def addText ( self , text : str ) -> None : self . left . extend ( list ( text )) def deleteText ( self , k : int ) -> int : k = min ( k , len ( self . left )) for _ in range ( k ): self . left . pop () return k def cursorLeft ( self , k : int ) -> str : k = min ( k , len ( self . left )) for _ in range ( k ): self . right . append ( self . left . pop ()) return '' . join ( self . left [ - 10 :]) def cursorRight ( self , k : int ) -> str : k = min ( k , len ( self . right )) for _ in range ( k ): self . left . append ( self . right . pop ()) return '' . join ( self . left [ - 10 :]) # Your TextEditor object will be instantiated and called as such: # obj = TextEditor() # obj.addText(text) # param_2 = obj.deleteText(k) # param_3 = obj.cursorLeft(k) # param_4 = obj.cursorRight(k)
```