Quick 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.

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.

Read the full Replit Software Engineer interview experience this question came from

A text editor records an editing session as an initial string `document` and a list of `keystrokes`. Implement `keystrokes_to_ops(document, keystrokes)`. The cursor starts at position 0, before the first character of the document. 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. 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. Each returned operation is a list of two strings, 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. Only the final effect of the session is reported, and 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` - Each keystroke is exactly one of `["type", text]`, `["backspace"]` or `["right"]`. - 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; no value in this problem exceeds `2^31 - 1`. **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 = "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`.

Constraints

  • 0 <= len(document) <= 10^5
  • 0 <= len(keystrokes) <= 10^5
  • Each keystroke is exactly one of ["type", text], ["backspace"] or ["right"].
  • 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

Input: ('', [])

Expected Output: []

Explanation: Minimum: empty document and no keystrokes, so nothing changes.

Input: ('abc', [])

Expected Output: []

Explanation: Non-empty document with no keystrokes has no effect.

Hints

  1. Keep track of where each character of the current text came from: a position in the initial document, or a keystroke that typed it.
  2. At the end of the session, the kept characters of the initial document split the final text into gaps; describe each gap by how many original characters vanished there and which typed text sits there.
  3. Apply the canonical rules last: merge neighbors of the same kind, put a gap's delete before its insert, and drop a trailing skip.

Loading coding console...

Show the approach

Approach

Simulate the session with two stacks (a gap buffer). The left stack holds the text before the cursor; the right stack holds the text after the cursor with the next character on top. Every item is tagged: a character of the initial document is stored as its index in document, and a typed character is stored as -1 minus its character code, so the two kinds never collide. Typing pushes the typed characters onto the left stack; backspace pops the left stack (an original index popped this way is a deleted character); right moves the top of the right stack onto the left stack. Backspace with an empty left stack (cursor at position 0) and right with an empty right stack (cursor at the end) do nothing.

Invariant: the cursor never moves left without deleting, so the right stack only ever holds untouched original characters in document order, and the original indices in the final text (left stack followed by the reversed right stack) are strictly increasing because the editor never reorders characters. An original character is missing from the final text exactly when a backspace removed it, and every typed character in the final text sits at its final position.

To build the canonical list, walk the final text once. Typed characters accumulate in a buffer. When a kept original index k is reached after the previous kept index prev (initially -1), the k - prev - 1 originals between them were deleted and the buffer holds exactly the text inserted in that same gap; if either is non-empty, emit the pending skip run, then the delete, then the insert (delete before insert), and reset the buffer. Each kept character extends the pending skip run, so adjacent skips merge; two gaps are always separated by at least one kept character, so no two deletes or two inserts can be adjacent. After the walk, the gap after the last kept character (n - prev - 1 deletions plus any buffered text) is flushed the same way, and a pending skip not followed by an edit is never emitted, so the list never ends with a skip. If nothing was deleted or inserted, nothing is emitted and the result is empty.

Edge cases: empty document and/or empty keystroke list; backspace at position 0 and right at the end of the text are no-ops; typed text that is later backspaced never reaches the final text; a deleted original retyped identically is still reported as a delete followed by an insert; deletions separated only by typed text that was later backspaced merge into one delete.

Time complexity:
O(n + m + T), where n = len(document), m = len(keystrokes) and T is the total length of typed text
Space complexity:
O(n + T)