Compress editor keystrokes into insert/delete/skip
Company: Replit
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Onsite
You are implementing a simplified collaborative editor sync format.
You are given:
- An initial document string `doc`.
- A list of user *input operations* (keystrokes) applied in order, with the cursor initially at the **start** of `doc`.
### Input operations
Each operation is one of:
- `append(c)`: insert character `c` at the cursor; cursor moves right by 1.
- `backspace()`: delete the character immediately to the **left** of the cursor (if any); cursor moves left by 1 if a deletion happened.
- `right()`: move the cursor right by 1 **if** it is not already at the end of the current document.
### Output operations
Convert the keystrokes into a compressed list of operations using only:
- `insert(s)`: insert string `s` at the cursor; cursor moves right by `len(s)`.
- `delete(k)`: delete `k` characters immediately to the **left** of the cursor (equivalent to pressing backspace `k` times).
- `skip(k)`: move the cursor right by `k`.
### Goal
Return an equivalent list of output operations that reproduces the same final document as the keystrokes, while **compressing** operations by:
1. Merging consecutive `append` keystrokes into a single `insert`.
2. Merging consecutive cursor moves into a single `skip`.
3. Merging consecutive deletions into a single `delete`.
4. Canceling when possible (e.g., an `append` followed by `backspace` should remove the appended character from the output script; a `right` followed later by `backspace` may turn that previously-skipped character into a deletion).
### Examples
1) `doc = ""`, input: `[append('a'), append('b'), append('c')]`
Output: `[insert("abc")]`
2) `doc = "aa"`, input: `[right(), backspace()]`
Output: `[delete(1)]`
3) `doc = "aa"`, input: `[right()]`
Output: `[skip(1)]`
Implement a function that performs this conversion.
(Assume inputs are such that you only need to handle the behaviors described above; you may ignore any cases not covered by the stated rules.)
Quick Answer: This question evaluates simulation of sequential editor operations and compression logic, assessing skills in string manipulation, state tracking, and sequence transformation within the Coding & Algorithms domain.
You are given an initial document string `doc` and a list of keystroke operations applied in order, with the cursor starting at the beginning of `doc`.
Each input operation is represented as a tuple:
- `("append", c)`: insert character `c` at the cursor, then move the cursor right by 1.
- `("backspace",)`: delete the character immediately to the left of the cursor, if any.
- `("right",)`: move the cursor right by 1 if it is not already at the end of the current document.
Convert this keystroke list into a compressed edit script using only these output operations:
- `("insert", s)`: insert string `s` at the current cursor position.
- `("delete", k)`: delete the next `k` original characters starting at the cursor.
- `("skip", k)`: keep the next `k` original characters and move past them.
The compressed script is a left-to-right edit script over the original document. It must produce the same final document and cursor position as the keystrokes.
Compression rules:
1. Merge consecutive appends into one `insert`.
2. Merge consecutive kept original characters into one `skip`.
3. Merge consecutive deleted original characters into one `delete`.
4. Cancel work when possible. For example, an appended character later removed by backspace should disappear from the output entirely.
Return the compressed list of output operations as tuples.
Constraints
- 0 <= len(doc) <= 2 * 10^5
- 0 <= len(operations) <= 2 * 10^5
- Each append operation uses a single-character string
- Expected solution should run in O(len(doc) + len(operations)) time
Examples
Input: ("", [("append", "a"), ("append", "b"), ("append", "c")])
Expected Output: [("insert", "abc")]
Explanation: Three consecutive appends merge into one insert.
Input: ("aa", [("right",), ("backspace",)])
Expected Output: [("delete", 1)]
Explanation: The first original character is crossed and then removed, so it becomes one delete.
Hints
- Simulate the editor as two parts: content to the left of the cursor and the untouched suffix of the original document. `right()` only moves the next original character into the left side.
- After simulation, every original character in the processed prefix is either still present before the cursor (`skip`) or was crossed and later removed (`delete`). Surviving inserted characters appear between them and become `insert` operations.