Maximize coins collected by tokens jumping +3
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
You are given a single-player board game represented by a string `board` of length `N` (1 ≤ N ≤ 100). Each character is one of:
- `'.'`: empty cell
- `'T'`: a player token (there may be multiple tokens)
- `'C'`: a coin
A move consists of selecting one token and moving it **exactly 3 positions to the right** (from index `i` to `i+3`). The token does not interact with intermediate cells.
Rules:
- A move is only allowed if `i+3 < N`.
- A move is **not** allowed if the destination cell currently contains another token (`'T'`).
- If a token lands on a cell containing a coin (`'C'`), that coin is collected and removed (each coin can be collected at most once).
- Tokens can be moved multiple times.
Task: Return the **maximum number of coins** that can be collected.
Function signature:
```python
def solution(board: str) -> int:
...
```
Examples:
- `board = "TT.T.CCCCC"` → `3`
- `board = "T...CCCC"` → `1`
- `board = "C..TT.CT.C"` → `2`
Quick Answer: Evaluates algorithmic reasoning about constrained discrete moves and optimization, focusing on state-space modeling, reachability under move constraints, and resource-maximization techniques.
You are given a single-player board game represented by a string `board` of length `N`. Each character is one of:
- `'.'`: empty cell
- `'T'`: a player token
- `'C'`: a coin
A move consists of selecting one token at index `i` and moving it exactly 3 positions to the right, from `i` to `i + 3`.
Rules:
- A move is only allowed if `i + 3 < N`.
- A move is not allowed if the destination cell currently contains another token (`'T'`).
- The token does not interact with the two intermediate cells.
- If a token lands on a cell containing a coin (`'C'`), that coin is collected and removed.
- Tokens may be moved multiple times.
Return the maximum number of coins that can be collected.
Constraints
- 1 <= len(board) <= 100
- Each character of `board` is one of '.', 'T', or 'C'
Examples
Input: "TT.T.CCCCC"
Expected Output: 3
Explanation: Split by indices modulo 3. Coins at indices 6, 7, and 9 each have a token earlier in the same lane, so they can be collected. Coins at 5 and 8 cannot.
Input: "T...CCCC"
Expected Output: 1
Explanation: Only the coin at index 6 is in the same modulo-3 lane as the token at index 0. The other coins are unreachable.
Hints
- A token that starts at index `i` can only ever visit positions with the same value of `index % 3`.
- For each modulo-3 lane, think about which coins are impossible to reach and which ones will definitely be visited once there is at least one token before them.