Design a Text Editor

hard doubly linked list stack design

Problem

Design a TextEditor with a cursor. addText(text) inserts text at the cursor (cursor ends to its right). deleteText(k) backspaces up to k characters to the left of the cursor and returns how many were actually deleted. cursorLeft(k) and cursorRight(k) move the cursor up to k steps (it always stays within the text) and each returns the last min(10, len) characters to the left of the cursor.

Input

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

Output[null, 4, null, "etpractice", "leet", 4, "", "practi"]

After deleting 4 the text is "leet|"; adding "practice" gives "leetpractice|". cursorRight(3) cannot move (already at end) so it returns the last 10 left chars "etpractice"; cursorLeft(8) lands on "leet|practice" returning "leet"; deleteText(10) removes only the 4 left chars → 4; cursorRight(6) gives "practi|ce" → "practi".

operations (op:arg, comma-separated; add:text, del:k, left:k, right:k)

class TextEditor:
    def __init__(self):
        self.left = []                         # chars left of cursor (top = nearest)
        self.right = []                        # chars right of cursor (top = nearest)

    def addText(self, text: str) -> None:
        for ch in text:                        # push each char onto the left stack
            self.left.append(ch)

    def deleteText(self, k: int) -> int:
        d = min(k, len(self.left))             # cannot delete past the start
        for _ in range(d):
            self.left.pop()
        return d

    def cursorLeft(self, k: int) -> str:
        m = min(k, len(self.left))             # cursor stays within the text
        for _ in range(m):                     # move chars from left to right
            self.right.append(self.left.pop())
        return "".join(self.left[-10:])        # last min(10, len) left chars

    def cursorRight(self, k: int) -> str:
        m = min(k, len(self.right))            # cursor stays within the text
        for _ in range(m):                     # move chars from right to left
            self.left.append(self.right.pop())
        return "".join(self.left[-10:])        # last min(10, len) left chars

class TextEditor {
  constructor() {
    this.left = [];                          // chars left of cursor (top = nearest)
    this.right = [];                         // chars right of cursor (top = nearest)
  }
  addText(text) {
    for (const ch of text) this.left.push(ch); // push each char onto left
  }
  deleteText(k) {
    const d = Math.min(k, this.left.length); // cannot delete past the start
    for (let i = 0; i < d; i++) this.left.pop();
    return d;
  }
  cursorLeft(k) {
    const m = Math.min(k, this.left.length); // cursor stays within text
    for (let i = 0; i < m; i++) this.right.push(this.left.pop());
    return this.left.slice(-10).join("");    // last min(10, len) left chars
  }
  cursorRight(k) {
    const m = Math.min(k, this.right.length);// cursor stays within text
    for (let i = 0; i < m; i++) this.left.push(this.right.pop());
    return this.left.slice(-10).join("");    // last min(10, len) left chars
  }
}

class TextEditor {
    private Deque<Character> left = new ArrayDeque<>();   // left of cursor
    private Deque<Character> right = new ArrayDeque<>();  // right of cursor

    public void addText(String text) {
        for (char ch : text.toCharArray()) left.push(ch);
    }
    public int deleteText(int k) {
        int d = Math.min(k, left.size());                // cannot delete past start
        for (int i = 0; i < d; i++) left.pop();
        return d;
    }
    public String cursorLeft(int k) {
        int m = Math.min(k, left.size());                // cursor stays in text
        for (int i = 0; i < m; i++) right.push(left.pop());
        return tail();
    }
    public String cursorRight(int k) {
        int m = Math.min(k, right.size());               // cursor stays in text
        for (int i = 0; i < m; i++) left.push(right.pop());
        return tail();
    }
    private String tail() {                              // last min(10, len) left chars
        int n = Math.min(10, left.size());
        char[] buf = new char[n];
        Iterator<Character> it = left.iterator();
        for (int i = n - 1; i >= 0; i--) buf[i] = it.next();
        return new String(buf);
    }
}

class TextEditor {
    string left, right;                       // left/right of cursor; left.back()=nearest
public:
    void addText(string text) {
        left += text;                         // append each char to the left
    }
    int deleteText(int k) {
        int d = min(k, (int)left.size());     // cannot delete past the start
        left.erase(left.end() - d, left.end());
        return d;
    }
    string cursorLeft(int k) {
        int m = min(k, (int)left.size());     // cursor stays within text
        while (m--) { right += left.back(); left.pop_back(); }
        return tail();
    }
    string cursorRight(int k) {
        int m = min(k, (int)right.size());    // cursor stays within text
        while (m--) { left += right.back(); right.pop_back(); }
        return tail();
    }
    string tail() {                           // last min(10, len) left chars
        int n = min(10, (int)left.size());
        return left.substr(left.size() - n);
    }
};

Explanation

The hard part of a text editor is that edits happen in the middle of the text, right where the cursor sits — and arbitrary middle insertions/deletions are expensive on a flat string. The trick is to split the text at the cursor into two stacks: a left stack holding everything to the left of the cursor and a right stack holding everything to its right.

The key invariant is orientation. The top of left is the character immediately left of the cursor, and the top of right is the character immediately right of the cursor. With this layout, the cursor is always "between the two stack tops", so every operation only ever touches the tops — which is exactly where stacks are fast.

addText pushes each new character onto left; the cursor naturally ends just after the inserted text. deleteText(k) pops up to k characters off left (never more than exist) and returns the actual count — this is the backspace key.

cursorLeft(k) moves up to k characters from the top of left to the top of right (the cursor slides left, characters cross over). cursorRight(k) does the mirror image, moving characters from right back to left. Both clamp k to the available length so the cursor never leaves the text.

After any cursor move we return the last min(10, len) characters to the left of the cursor — that is just the bottom-to-top tail of the left stack. Because every call moves at most k characters and copies at most 10 for the return value, each operation is O(k), satisfying the follow-up. The same idea can be implemented with a doubly linked list, which is why this is a classic linked-list design exercise.

Time: O(k) per call Space: O(n) total characters