Asked in: MICROSOFT
Image of the Question
All Testcases Passed ✔
Solution
#include <iostream>
#include <vector>
#include <string>
#include <deque>
// ... rest of solution available after purchaseExplanation
```
To solve the problem of implementing a prototype text editor that supports various editing commands and querying the text content near the cursor, the key is to efficiently maintain and manipulate the current text state and the cursor position throughout the operations.
---
Step 1: Understand the Data Structure Needed
- The text is a mutable sequence of characters where insertions, deletions, and cursor movements happen frequently.
- A common naive approach would be to represent the text as a single string and modify it directly.
- However, in many languages, strings are immutable or expensive to modify frequently, especially if done naively (e.g., repeatedly slicing and concatenating).
- Since the maximum total inserted text length is up to 5000, performance constraints are moderate but still require a careful approach to avoid O(n) operations repeatedly.
- A suitable approach is to use two stacks or lists representing characters to the left and right of the cursor, sometimes called a "cursor buffer" or "gap buffer" approach.
---
Step 2: Model the Cursor and Text Using Two Lists
- Maintain two sequences:
- Left part: characters before the cursor (in order).
- Right part: characters after the cursor (in order).
- Cursor position implicitly exists between these two sequences.
- Insertions add characters to the left sequence (at the cursor position), effectively moving the cursor right after the inserted text.
- Moving cursor left/right moves characters between the left and right sequences.
- Backspace removes characters from the left sequence (characters before the cursor).
- Delete removes characters from the right sequence (characters after the cursor).
- This data structure allows O(1) or O(x) operations for cursor movements and edits, avoiding costly string copies.
---
Step 3: Implementing Each Command
- Insert s:
- Append all characters of s to the left sequence.
- Cursor moves right by length of s (already handled as left sequence grows).
- Left x:
- Move min(x, len(left)) characters from left to right sequence.
- This simulates moving cursor left but prevents moving beyond start of string.
- Right x:
- Move min(x, len(right)) characters from right to left sequence.
- Cursor moves right but not past end of string.
- Backspace x:
- Remove min(x, len(left)) characters from the end of the left sequence.
- Cursor moves left accordingly as characters are removed.
- Delete x:
- Remove min(x, len(right)) characters from the start of the right sequence.
- Cursor position unchanged.
- Print x:
- The cursor is between left and right sequences.
- Need to print substring from (cursor - x) to (cursor + x) inclusive, adjusting for boundaries.
- This requires concatenating relevant parts of left and right sequences.
- For indices before the cursor, take the last min(x, len(left)) characters from the left sequence.
- For indices after the cursor, take the first min(x, len(right)) characters from the right sequence.
- Combine those to form the substring and record the output.
---
Step 4: Handle Boundaries and Edge Cases
- When moving cursor left or right, never move beyond string boundaries.
- When deleting or backspacing, only remove characters if available.
- When printing, adjust the start and end indices to valid ranges within the total string length.
- Since the cursor is between left and right sequences, the "cursor position" is effectively the length of the left sequence.
- Empty strings and zero-length removals should be gracefully handled.
---
Step 5: Efficient String Manipulation
- Using two lists for left and right characters ensures that insertions and removals are efficient.
- Most operations translate to appending or popping elements from these lists, which is efficient in common programming languages.
- For the print operation, slicing the lists is straightforward.
- The complexity per command is mostly O(x), where x is the parameter in the command, which is acceptable given the constraints.
---
Step 6: Process Commands in Order
- Initialize the editor with empty left and right lists, cursor at position 0.
- For each command in the given sequence:
- Parse the command and parameter.
- Convert parameters to integers where needed.
- Perform the operation using the two-list model.
- For "Print" commands, collect the output string in a results list.
- After processing all commands, return the list of printed substrings.
---
Step 7: Example Walkthrough
Consider the sample input:
Commands:
1) Insert "addthis" → left = ['a','d','d','t','h','i','s'], right = [], cursor at 7.
2) Print 5 → substring from index 2 to 12 (clamped), take last 5 chars from left and first 5 from right (right is empty), print "dthis".
3) Left 4 → move 4 chars from left to right, left now ['a','d','d'], right ['t','h','i','s'], cursor at 3.
4) Right 2 → move 2 chars from right to left, left ['a','d','d','t','h'], right ['i','s'], cursor at 5.
5) Backspace 1 → remove 1 char from left, left ['a','d','d','t'], cursor at 4.
6) Delete 1 → remove 1 char from right, right ['s'].
7) Print 10 → substring indices from max(0,4-10)=0 to min(len=5+1=6,4+10=14)=6, take last 4 chars from left plus all from right → "addts".
---
Step 8: Summary
- Use two separate character lists to model text before and after the cursor.
- Move characters between lists to simulate cursor moves.
- Insert and remove characters by appending/popping in these lists.
- Compute print output by combining slices from both lists considering boundaries.
- This approach leads to a clear, efficient, and maintainable implementation that handles all specified operations within constraints.
```