DSA problem
Design a Text Editor
Design a text editor with a cursor that supports four operations: addText(text) inserts text at the current cursor position and shifts the cursor right by text.length. deleteText(k) deletes up to k characters immediately to the left of the cursor and returns the number actually deleted. cursorLeft(k) moves the cursor up to k positions left and returns the last (up to) 10 characters that now lie to the left of the cursor. cursorRight(k) is the mirror, moving the cursor up to k positions right.
A naive implementation using a single string is too slow: every insert and delete in the middle of a string is O(n), which is unacceptable for 2 * 10^5 operations on a string that can grow to 4 * 10^4 characters. The classic trick for "edit at the cursor" is the two-stack model — represent the document as two stacks: left is everything to the left of the cursor (top = nearest to cursor), and right is everything to the right of the cursor (top = nearest to cursor).
In this model, addText(s) is simply pushing the characters of s onto left — O(|s|). deleteText(k) is popping up to k characters off left — O(k) amortized. cursorLeft(k) transfers up to k characters from left to right one at a time, which physically moves the cursor to the left. cursorRight(k) is the mirror — pop from right, push onto left. Each character is moved at most twice between the stacks across the lifetime of a query, so the amortized cost is O(1) per character of motion.
After every cursorLeft / cursorRight we need to return the last (up to) 10 characters left of the cursor. Because left is a stack with the most-recent character at the top, those 10 characters are simply the top 10 of left in their stored order — easy to read in O(10). Both stack-based operations are trivially O(k) per call, but the editor as a whole is O(total operations) — exactly the bound the problem requires.
Examples
addText("leetcode"); deleteText(4); addText("practice"); cursorRight(3); cursorLeft(8); deleteText(10); cursorLeft(2); cursorRight(6)4, "etpractice", "leet", "", "practi"addText("hello"); cursorLeft(3); addText("xy")— state onlydeleteText(5) on an empty editor0Constraints
- 1 <= text.length, k <= 40
- text consists of lowercase English letters.
- At most 2 * 10^4 calls in total will be made to addText, deleteText, cursorLeft, and cursorRight.
- cursorLeft and cursorRight return at most 10 characters.
- Total characters in the document stay within reasonable bounds (a few * 10^5).
4 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.