Convert Editor Keystrokes into a Minimal Insert, Delete and Skip Operation List
Company: Replit
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
A text editor records an editing session as an initial document and a list of keystrokes. The cursor starts at position 0, before the first character of the document. There are three kinds of keystroke: typing text at the cursor, backspace (delete the character just before the cursor), and moving the cursor one character to the right.
Convert the session into the shortest list of operational-transform (OT) operations that describes its final effect on the initial document. An operation list is read from left to right with its own cursor over the initial document, which starts at position 0:
- `["skip", n]` keeps the next `n` characters of the initial document and moves past them.
- `["delete", n]` removes the next `n` characters of the initial document and moves past them.
- `["insert", text]` inserts `text` at the current position.
Characters of the initial document that remain after the last operation are kept. Only the final effect of the session is reported: text that was typed and later backspaced does not appear in the result.
### Function Signature
```python
def keystrokes_to_ops(document: str, keystrokes: list[list[str]]) -> list[list[str]]:
```
### Rules
- Each keystroke is one of:
- `["type", text]`: inserts `text` at the cursor and leaves the cursor just after it.
- `["backspace"]`: deletes the character immediately before the cursor, and the cursor moves back by one. Does nothing when the cursor is at position 0.
- `["right"]`: moves the cursor one character to the right. Does nothing when the cursor is at the end of the current text.
- Each returned operation is a list of two strings: `["skip", n]`, `["delete", n]` or `["insert", text]`, where `n` is a positive count written in decimal without leading zeros (for example `["skip", "12"]`) and `text` is non-empty.
- Applying the returned operations to `document` must produce the text at the end of the session.
- The operations report what happened to each character, not only how the text looks at the end:
- A character of the initial document is deleted exactly when a backspace removed it; every other character of the initial document is kept.
- A deleted character stays deleted even if the same character is typed again later; the retyped character is inserted.
- Every typed character still present at the end of the session appears in exactly one `insert`, at its final position. Typed characters that were backspaced appear nowhere.
- The result is the unique canonical list for that effect:
- No two adjacent operations have the same kind; adjacent operations of one kind are merged into one.
- When deleted characters and inserted text fall between the same two neighboring kept characters (or before the first kept character, or after the last one), the `delete` comes before the `insert`.
- The list never ends with a `skip`; kept characters at the end are implied.
- Return an empty list when the session deletes nothing and inserts nothing.
### Constraints
- `0 <= len(document) <= 10^5`
- `0 <= len(keystrokes) <= 10^5`
- Every `["type", text]` keystroke has `len(text) >= 1`, and the total length of all typed text is at most `10^5`.
- `document` and every typed `text` contain only English letters, digits and spaces.
- Every count in the output is at most `10^5`, so it fits in a 32-bit signed integer.
### Examples
**Example 1**
```text
Input: document = "abcdef"
keystrokes = [["right"], ["right"], ["type", "XY"], ["right"], ["backspace"], ["backspace"], ["type", "Z"]]
Output: [["skip", "2"], ["delete", "1"], ["insert", "XZ"]]
```
After two moves to the right the text is `ab|cdef` (`|` marks the cursor). Typing gives `abXY|cdef`, and moving right gives `abXYc|def`. The first backspace removes the original `c`, the second removes the typed `Y`, and typing `Z` gives `abXZ|def`. Between the kept `b` and the kept `d`, the original `c` was deleted and `XZ` was inserted, so the delete comes first; the trailing `def` is kept without a `skip`.
**Example 2**
```text
Input: document = "hello"
keystrokes = [["type", "abc"], ["backspace"], ["backspace"], ["backspace"], ["right"], ["right"]]
Output: []
```
The typed `abc` is backspaced entirely, and moving the cursor changes nothing, so the session has no effect.
**Example 3**
```text
Input: document = "abc"
keystrokes = [["backspace"], ["right"], ["backspace"], ["type", "a"], ["right"], ["right"], ["right"], ["type", "d"]]
Output: [["delete", "1"], ["insert", "a"], ["skip", "2"], ["insert", "d"]]
```
The first backspace does nothing because the cursor is at position 0, and the last move to the right does nothing because the cursor is already at the end. The original `a` was backspaced, so it is reported as deleted even though an `a` was typed back in its place. The final text is `abcd`.
Overview: Convert a text editor session of typed text, backspaces and right-arrow moves into the shortest list of insert, delete and skip operations over the original document. It tests careful cursor simulation, cancelling typed text that was later erased, and producing one canonical, merged operation list.
