Maximize coins collected by 3-step pieces
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given a 1D board of length **N**. Each cell is in one of three states:
- **Empty**
- **Piece** (a movable token)
- **Coin** (collectible)
In one move, you may choose **any one piece** and move it **exactly 3 cells to the right** (from index `i` to `i+3`). The move rules are:
1. If the destination cell is **empty**, the piece moves there.
2. If the destination cell contains a **coin**, the piece moves there and you **collect** that coin (the coin is removed).
3. Pieces **cannot overlap**: a move is **not allowed** if the destination cell already contains another piece.
4. The piece may “jump over” intervening cells; only the destination cell matters.
5. A move is not allowed if `i+3` is outside the board.
You may perform moves in any order, for as many turns as you like, until **no piece can legally move**.
Return the **maximum number of coins** you can collect.
### Input
- A representation of the board (e.g., a string/array of length `N`) containing exactly one of `{empty, piece, coin}` per cell.
### Output
- An integer: the maximum number of coins collectible.
### Notes / Clarifications
- Multiple pieces may exist.
- Coins are collected at most once (they disappear after collection).
- The result depends on the order in which you choose moves.
Quick Answer: This question evaluates modeling and optimization of discrete state-space transitions under movement constraints, testing combinatorial reasoning, reachability, and resource-maximization competencies.
You are given a 1D board of length N, represented as a string where each character is one of: '.' (empty cell), 'P' (a movable piece), or 'C' (a collectible coin).
In one move you may pick any one piece at index i and move it exactly 3 cells to the right (to i+3). The rules:
1. The move is only legal if i+3 < N (cannot move off the board).
2. If the destination cell is empty, the piece moves there.
3. If the destination cell holds a coin, the piece moves there and that coin is collected (removed from the board).
4. Pieces cannot overlap: a move is illegal if i+3 already holds another piece.
5. A piece jumps over intervening cells; only the destination cell matters.
You may perform moves in any order, for as many turns as you like, until no piece can legally move. Return the maximum number of coins you can collect.
Key observation: a move of +3 keeps every piece inside its own residue class mod 3, so the board splits into three independent sub-lines. Within each sub-line (where a move becomes one step right), pieces keep their relative order, so the j-th of k pieces can advance to at most position m-1-(k-1-j); a coin is collectible exactly when some piece can sweep over it.
Constraints
- 1 <= N <= 10^5 (board length)
- Each board character is one of '.', 'P', or 'C'.
- 0 or more pieces and 0 or more coins may be present.
- A piece moves only to the right, exactly 3 cells per move.
- Each coin is collected at most once.
Examples
Input: ('P..C',)
Expected Output: 1
Explanation: Piece at 0 moves +3 onto the coin at 3 and collects it.
Input: ('P..C..C',)
Expected Output: 2
Explanation: Piece sweeps 0->3 (coin) then 3->6 (coin); both coins lie 3 apart so both are collected.
Hints
- A move always changes an index by +3, so a piece can only ever visit cells sharing its index's value mod 3. The three residue classes never interact - solve each independently and sum the results.
- Compress one residue class into consecutive slots; a move becomes a single step to the right. Pieces preserve their order because they only move right and cannot overlap.
- In a compressed line of length m with k pieces, the j-th piece (0-indexed from the left) can be pushed as far as slot m-1-(k-1-j) once the pieces to its right vacate the end. A coin is collectible iff some piece's start <= coin <= that piece's max reach.