2296. Design a Text Editor

On LeetCode ->

class TextEditor:
    def __init__(self):
        pass

    def addText(self, text: str) -> None:
        pass

    def deleteText(self, k: int) -> int:
        pass

    def cursorLeft(self, k: int) -> str:
        pass

    def cursorRight(self, k: int) -> str:
        pass

Problem¶

Maintain text and a cursor, initially empty. Implement:

addText(text): insert text at the cursor; move past it.
deleteText(k): backspace up to k characters; return how many were deleted.
cursorLeft(k) / cursorRight(k): move up to k positions without leaving the text; return the last at most 10 characters before the cursor.

Operation       Text state    Return
initial         |             -
addText("abc")  abc|          None
cursorLeft(2)   a|bc          "a"
addText("xy")   axy|bc        None
deleteText(2)   a|bc          2
cursorRight(9)  abc|          "abc"

Key trick¶

Use two stacks: left holds the prefix normally, and right holds the suffix reversed, so moving the cursor transfers characters between stack tops.

Trap¶

Keep the right stack reversed, clamp movement and deletion at the boundaries, and return only the last 10 characters before the cursor. Rebuilding a full string per operation costs \(O(n)\).

Why is it interesting?¶

A cursor turns arbitrary-position editing into efficient stack operations when the data representation follows the cursor.

Python solution¶

class TextEditor:
    def __init__(self):
        # Text is left + reversed(right); the cursor lies between them.
        self.left = []
        self.right = []

    def addText(self, text: str) -> None:
        self.left.extend(text)

    def deleteText(self, k: int) -> int:
        cnt = min(k, len(self.left))
        for _ in range(cnt):
            self.left.pop()
        return cnt

    def cursorLeft(self, k: int) -> str:
        for _ in range(min(k, len(self.left))):
            self.right.append(self.left.pop())
        return "".join(self.left[-10:])

    def cursorRight(self, k: int) -> str:
        for _ in range(min(k, len(self.right))):
            self.left.append(self.right.pop())
        return "".join(self.left[-10:])

Time: addText takes amortized \(O(t)\) for \(t\) inserted characters; deletion and cursor movement take amortized \(O(k)\) per call.

Space: \(O(n)\) for the current text; returning the preview uses \(O(1)\) additional space.

Comment on my solution¶

Your solution is correct and meets the \(O(k)\) follow-up.

A deque is valid, but not necessary: storing the right side reversed allows a second list stack.
Replace the insertion loop with self.left.extend(text).
Replace the preview calculation with "".join(self.left[-10:]).

# Ideas:
# - have to blocks which contains
#   - what is before the cursor
#   - and after the cursor
# - each time the cursor move we transfer characters from one block to the other
#
# leetpractice|
# left = [leetpractice]
# right = []
# move to left 3
# left = [leetpract]
# right = [ice]
# move to right 1
# left = [leetpracti]
# right = [ce]
# delete 4
# left = [leetpr]
# right = [ce]
#
# - It seems that left is just a stack and right must be a deque

from collections import deque

# WORKS
class TextEditor:
    def __init__(self):
        self.left = []
        self.right = deque()

    def addText(self, text: str) -> None:
        for ch in text:
            self.left.append(ch)

    def deleteText(self, k: int) -> int:
        deleted = 0
        while self.left and k:
            deleted += 1
            self.left.pop()
            k -= 1
        return deleted

    def cursorLeft(self, k: int) -> str:
        while self.left and k:
            self.right.appendleft(self.left.pop())
            k -= 1
        start = len(self.left) - min(10, len(self.left))
        return "".join(self.left[start:])

    def cursorRight(self, k: int) -> str:
        while self.right and k:
            self.left.append(self.right.popleft())
            k -=1
        start = len(self.left) - min(10, len(self.left))
        return "".join(self.left[start:])