Can board states be transformed?
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given two strings, `start` and `target`, of equal length representing a one-dimensional board.
Each character is one of:
- `L`: a piece that may move only to the left
- `R`: a piece that may move only to the right
- `_`: an empty cell
- `|`: a wall
Rules:
- In one move, a piece may slide into an adjacent empty cell in its allowed direction.
- `L` pieces can never move right.
- `R` pieces can never move left.
- Walls `|` are fixed, cannot move, and no piece may cross a wall.
Determine whether `start` can be transformed into `target` using any number of valid moves.
Also explain how the simpler version changes when there are no walls and the strings contain only `L`, `R`, and `_`.
Quick Answer: This question evaluates reasoning about constrained piece movement, string transformation, and invariant-based correctness in the Coding & Algorithms domain, testing skills in string manipulation and combinatorial reasoning while examining both conceptual properties and practical algorithmic implementation.