Decide string transform with directional tokens and walls
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given two equal-length strings start and target of length n, each consisting only of the characters 'L', 'R', '.', and 'X'. A dot '.' represents an empty slot; 'X' represents an immovable wall; 'L' and 'R' are tokens that may move across empty slots subject to these rules:
(
1) An 'L' token may move any number of positions left into '.', but may never move right, pass through another token, or pass through an 'X'.
(
2) An 'R' token may move any number of positions right into '.', but may never move left, pass through another token, or pass through an 'X'.
(
3) Only one token can occupy a position at any time. Determine whether target can be obtained from start by a sequence of valid moves. If yes, return true; otherwise, return false. Design an algorithm that runs in O(n) time and O(
1) extra space beyond a few pointers/counters. Explain your invariants, prove correctness informally, analyze time and space complexity, and walk through a few tricky edge cases (e.g., mismatched wall layouts, blocks separated by walls, consecutive tokens with no gaps).
Quick Answer: Decide string transform with directional tokens and walls evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
You are given two equal-length strings `start` and `target` of length n, each consisting only of the characters 'L', 'R', '.', and 'X'.
- '.' is an empty slot.
- 'X' is an immovable wall.
- 'L' is a token that may move any number of positions **left** into '.' cells, but may never move right, pass through another token, or pass through an 'X'.
- 'R' is a token that may move any number of positions **right** into '.' cells, but may never move left, pass through another token, or pass through an 'X'.
- At most one token can occupy a position at any time.
Return `true` if `target` can be obtained from `start` by a sequence of valid moves, otherwise `false`.
**Key observations**
1. Removing every '.', the remaining sequence of non-dot characters (the 'L'/'R' tokens and the 'X' walls) must be identical in `start` and `target`, in the same order — moves can neither create/destroy tokens nor reorder them past one another or past a wall.
2. For each matched 'L', its index in `start` must be `>=` its index in `target` (it can only slide left).
3. For each matched 'R', its index in `start` must be `<=` its index in `target` (it can only slide right).
4. For each matched 'X' wall, its index must be identical in `start` and `target` (walls never move).
A single left-to-right two-pointer scan that skips dots and compares the k-th non-dot character of each string enforces all of the above in O(n) time and O(1) extra space.
Constraints
- 1 <= n <= 10^5 (n may also be 0 for the empty-string edge case)
- len(start) == len(target)
- start and target consist only of the characters 'L', 'R', '.', and 'X'
- Required: O(n) time and O(1) extra space
Examples
Input: ('R...L', 'RL...')
Expected Output: True
Explanation: Non-dot sequences both 'RL'. R stays at index 0 (0<=0). L moves left from index 4 to index 1 (4>=1). All moves valid.
Input: ('R.L', 'R..L')
Expected Output: False
Explanation: Different lengths (3 vs 4) — immediately false.
Hints
- Strip the dots conceptually: the ordered sequence of non-dot characters (tokens and walls) must be identical in both strings — moves can never reorder them or change the count.
- Use two pointers, one per string, each skipping '.' cells, and compare the k-th non-dot character of start against the k-th of target.
- Direction constraints become index comparisons: an 'L' may only move left so its start index must be >= its target index; an 'R' may only move right so start index must be <= target index; an 'X' wall must keep the exact same index.