Design a Text Editor

• 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)).

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.

1class TextEditor {2    StringBuilder sb;3    int cursor;4 5    public TextEditor() {6        sb = new StringBuilder();7        cursor = 0;8    }9 10    public void addText(String text) {11        sb.insert(cursor, text);12        cursor += text.length();13    }14 15    public int deleteText(int k) {16        int start = Math.max(0, cursor - k);17        int end = cursor;18        if (start == end) return 0;19        int deletedCount = end - start;20        sb.delete(start, end);21        cursor = start;22        return deletedCount;23    }24 25    private String getLeftText() {26        int start = Math.max(0, cursor - 10);27        return sb.substring(start, cursor);28    }29 30    public String cursorLeft(int k) {31        cursor = Math.max(0, cursor - k);32        return getLeftText();33    }34 35    public String cursorRight(int k) {36        cursor = Math.min(sb.length(), cursor + k);37        return getLeftText();38    }39}

• 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.

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.

1class TextEditor {2    class Node {3        char c;4        Node prev, next;5        Node(char c) { this.c = c; }6    }7 8    Node cursor; // Node to the right of the conceptual cursor9    Node head, tail; // Sentinel nodes10 11    public TextEditor() {12        head = new Node(' ');13        tail = new Node(' ');14        head.next = tail;15        tail.prev = head;16        cursor = tail;17    }18 19    public void addText(String text) {20        for (char ch : text.toCharArray()) {21            Node newNode = new Node(ch);22            Node prevNode = cursor.prev;23            prevNode.next = newNode;24            newNode.prev = prevNode;25            newNode.next = cursor;26            cursor.prev = newNode;27        }28    }29 30    public int deleteText(int k) {31        int count = 0;32        for (int i = 0; i < k && cursor.prev != head; i++) {33            Node toDelete = cursor.prev;34            toDelete.prev.next = cursor;35            cursor.prev = toDelete.prev;36            count++;37        }38        return count;39    }40 41    private String getLeftText() {42        StringBuilder sb = new StringBuilder();43        Node curr = cursor.prev;44        for (int i = 0; i < 10 && curr != head; i++) {45            sb.append(curr.c);46            curr = curr.prev;47        }48        return sb.reverse().toString();49    }50 51    public String cursorLeft(int k) {52        for (int i = 0; i < k && cursor.prev != head; i++) {53            cursor = cursor.prev;54        }55        return getLeftText();56    }57 58    public String cursorRight(int k) {59        for (int i = 0; i < k && cursor != tail; i++) {60            cursor = cursor.next;61        }62        return getLeftText();63    }64}

• Use two StringBuilders: 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.

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 StringBuilders, 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 StringBuilders, leveraging their amortized constant-time performance for append and delete-at-end operations.

1class TextEditor {2    StringBuilder left;  // Text to the left of the cursor3    StringBuilder right; // Text to the right of the cursor, in reverse order4 5    public TextEditor() {6        left = new StringBuilder();7        right = new StringBuilder();8    }9 10    public void addText(String text) {11        left.append(text);12    }13 14    public int deleteText(int k) {15        int actualDeleted = Math.min(k, left.length());16        left.setLength(left.length() - actualDeleted);17        return actualDeleted;18    }19 20    private String getLeftText() {21        int len = left.length();22        return left.substring(Math.max(0, len - 10));23    }24 25    public String cursorLeft(int k) {26        int count = Math.min(k, left.length());27        for (int i = 0; i < count; i++) {28            right.append(left.charAt(left.length() - 1));29            left.deleteCharAt(left.length() - 1);30        }31        return getLeftText();32    }33 34    public String cursorRight(int k) {35        int count = Math.min(k, right.length());36        for (int i = 0; i < count; i++) {37            left.append(right.charAt(right.length() - 1));38            right.deleteCharAt(right.length() - 1);39        }40        return getLeftText();41    }42}