2296. Text Editor

Design a Text Editor

Think of this cursor as a dividing line:

the left side uses a LIFO stack,

the right side uses a deque that supports insertion and removal at front.

This way, no matter where the cursor moves or how far it slides, characters can be transferred between stack and deque with ease.

Methods to Implement

addText(string text)

Push the entire text onto the left stack.

Time complexity: $O(|\text{text}|)$

deleteText(int k)

Delete min(k, len(stack)) characters from the top of left stack.

Actual deletion count to return is min(k, len(stack)).

Time complexity: $O(k)$

cursorLeft(int k)

Moving the cursor left by $k$ positions means our dividing line cuts off some left side characters, so characters near the top of left stack now are characters near the front of right deque.

Pop min(k, len(stack)) characters from the top of left stack one by one, and push each into the front of right deque.

After these pops, go to the top of left stack to slice substring consisting of min(10, len(stack)) characters going leftward from there.

Time complexity: $O(k)$

cursorRight(int k)

Moving the cursor right by $k$ positions means our dividing line cuts off some right side characters, characters near the front of right deque now become characters near the top of left stack.

Pop min(k, len(Deque)) characters from the front of right deque one by one, and push each onto the top of left stack.

After these pops, go to the top of left stack to slice substring consisting of min(10, len(stack)) characters going leftward from there.

Time complexity: $O(k)$

Space complexity: $O(n)$, where $n$ is total number of characters on both sides of the cursor.

C++

#include <deque>
#include <string>
#include <vector>
using namespace std;

class TextEditor // LeetCode Q.2296.
{
private:
    deque<char> cursorLeftSide, cursorRightSide;

    string sliceCursorLeftTail() {
        string text = "";

        int startIdx = 0;
        if (cursorLeftSide.size() > 10)
            startIdx += cursorLeftSide.size() - 10;

        for (int idx = startIdx; idx < cursorLeftSide.size(); idx++)
            text += cursorLeftSide[idx];

        return text;
    }

public:
    TextEditor() {}

    void addText(string text) {
        for (const auto& letter : text)
            cursorLeftSide.push_back(letter);
    }

    int deleteText(int k) {
        int deletionsCount = cursorLeftSide.size();
        if (k < deletionsCount)
            deletionsCount = k;

        while (k > 0 && !cursorLeftSide.empty()) {
            cursorLeftSide.pop_back();
            k--;
        }

        return deletionsCount;
    }

    string cursorLeft(int k) {
        while (k > 0 && !cursorLeftSide.empty()) {
            char letter = cursorLeftSide.back();
            cursorRightSide.push_front(letter);
            cursorLeftSide.pop_back();
            k--;
        }

        return sliceCursorLeftTail();
    }

    string cursorRight(int k) {
        while (k > 0 && !cursorRightSide.empty()) {
            char letter = cursorRightSide.front();
            cursorLeftSide.push_back(letter);
            cursorRightSide.pop_front();
            k--;
        }

        return sliceCursorLeftTail();
    }
};

Python

from collections import deque


class TextEditor:  # LeetCode Q.2296.
    def __init__(self) -> None:
        self.cursor_left_side: deque[str] = deque([])
        self.cursor_right_side: deque[str] = deque([])

    def _slice_cursor_left_tail(self) -> str:        
        start_idx = max(0, len(self.cursor_left_side) - 10)

        text = ""
        for idx in range(start_idx, len(self.cursor_left_side)):
            text += self.cursor_left_side[idx]

        return text

    def add_text(self, text: str) -> None:
        self.cursor_left_side.extend(list(text))

    def delete_text(self, k: int) -> int:
        deletions_count = min(k, len(self.cursor_left_side))

        while k > 0 and self.cursor_left_side:
            self.cursor_left_side.pop()
            k -= 1
        
        return deletions_count

    def cursor_left(self, k: int) -> str:
        while k > 0 and self.cursor_left_side:
            char = self.cursor_left_side.pop()
            self.cursor_right_side.appendleft(char)
            k -= 1
        
        return self._slice_cursor_left_tail()

    def cursor_right(self, k: int) -> str:
        while k > 0 and self.cursor_right_side:
            char = self.cursor_right_side.popleft()
            self.cursor_left_side.append(char)
            k -= 1
        
        return self._slice_cursor_left_tail()