Design A Text Editor: Strings interview problem

01 · Problem

Design a simple text editor with a cursor. The cursor always sits between two characters (or at either end of the text), and it can never move outside the text.

Implement the TextEditor class:

TextEditor() creates an editor holding empty text with the cursor at position 0.
void addText(string text) inserts text at the cursor. The cursor ends up immediately to the right of the inserted text.
int deleteText(int k) deletes up to k characters to the left of the cursor (like pressing backspace k times) and returns the number of characters actually removed.
string cursorLeft(int k) moves the cursor left by up to k positions, stopping at the start of the text. It returns the last min(10, len) characters to the left of the cursor after the move, where len is the number of characters left of the cursor (an empty string if there are none).
string cursorRight(int k) moves the cursor right by up to k positions, stopping at the end of the text, and returns the same 10-character window as cursorLeft.

Can you make every call run in O(k) time?

02 · Examples

Example 01

Input

["TextEditor","addText","cursorLeft","deleteText","addText","cursorRight"], [[],["helloworld"],[5],[2],["xy"],[10]]

Output

[null,null,"hello",2,null,"helxyworld"]

Start empty. addText("helloworld") puts the cursor at the end. cursorLeft(5) moves it between "hello" and "world" and returns "hello". deleteText(2) removes "lo" and returns 2, leaving "hel|world". addText("xy") gives "helxy|world". cursorRight(10) can only move 5 steps to the end of the 10-character text and returns all 10 characters, "helxyworld".

Example 02

Input

["TextEditor","addText","deleteText","cursorLeft","addText","cursorRight","deleteText"], [[],["abcdefghijklm"],[20],[3],["code"],[2],[1]]

Output

[null,null,13,"",null,"code",1]

deleteText(20) can only remove the 13 existing characters and returns 13. cursorLeft(3) on empty text returns "". addText("code") gives "code|". cursorRight(2) cannot move and returns "code". deleteText(1) removes "e" and returns 1.

Example 03

Input

["TextEditor","addText","cursorLeft","addText","cursorLeft","cursorRight"], [[],["abcdefghijklmn"],[2],["z"],[20],[3]]

Output

[null,null,"cdefghijkl",null,"","abc"]

After "abcdefghijklmn" and cursorLeft(2) the 10 characters left of the cursor are "cdefghijkl". Inserting "z" yields "abcdefghijklz|mn". cursorLeft(20) stops at position 0 and returns "". cursorRight(3) moves to after "abc" and returns "abc".

03 · Constraints

011 <= text.length, k <= 40
02text consists only of lowercase English letters
03At most 2 * 10⁴ calls in total are made to addText, deleteText, cursorLeft and cursorRight

04 · Optimal complexity

Time: O(k) per operation
Space: O(n)

01 · Problem

02 · Examples

03 · Constraints

04 · Optimal complexity

Practice it alone or rehearse it as an interview.