Compute max coins with 3-step token moves
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Take-home Project
You are given a one-dimensional board with **n** positions represented by a string `s` of length `n`:
- `.` = empty cell
- `T` = token
- `C` = coin
You may move tokens any number of times under these rules:
1. A move selects one token and moves it **exactly 3 positions to the right** (from index `i` to `i+3`).
2. A token **cannot** move if `i+3` is outside the board.
3. A token **cannot** land on a cell currently occupied by another token (`T`).
4. If a token lands on a coin (`C`), that coin is collected (removed) and cannot be collected again.
Your task is to compute the **maximum number of coins** that can be collected by choosing an optimal sequence of moves.
**Input:** `s` (string of length `n`, consisting only of `.`, `T`, `C`)
**Output:** An integer = maximum coins collectible.
**Notes / clarifications:**
- Tokens can be moved in any order.
- A token may move multiple times.
- Coins are only collected when a token *lands* on them (not when jumping over them).
Quick Answer: This question evaluates combinatorial optimization, state-space reasoning, and algorithmic design for constrained token movements on a linear board, and falls under the Coding & Algorithms domain.
You are given a one-dimensional board with **n** positions represented by a string `s` of length `n`:
- `.` = empty cell
- `T` = token
- `C` = coin
You may move tokens any number of times under these rules:
1. A move selects one token and moves it **exactly 3 positions to the right** (from index `i` to `i+3`).
2. A token **cannot** move if `i+3` is outside the board.
3. A token **cannot** land on a cell currently occupied by another token (`T`).
4. If a token lands on a coin (`C`), that coin is collected (removed) and cannot be collected again.
Return the **maximum number of coins** that can be collected by choosing an optimal sequence of moves.
**Input:** `s` — a string of length `n` consisting only of `.`, `T`, `C`.
**Output:** an integer, the maximum number of coins collectible.
**Notes / clarifications:**
- Tokens can be moved in any order, and a token may move multiple times.
- Coins are only collected when a token *lands* on them (not when jumping over them).
**Key observation:** Because every move shifts a token by exactly +3, a token at index `i` can only ever occupy cells with the same residue `i mod 3`. So the board decomposes into three independent sub-lines (one per residue class mod 3); a token only collects coins in its own residue class. Within a residue class, view the cells of that residue as a compacted sub-line where each move advances a token by one sub-step. Since a token lands on every sub-cell it passes through, sweeping a token to the right collects every still-uncollected coin between its start and final sub-position. Tokens preserve their relative order (they cannot land on one another), so pack them toward the right end: the rightmost token may sweep to the last sub-cell, the next can sweep up to just before it, and so on. Sum the distinct coins collected across all three residue classes.
Constraints
- 0 <= n <= 10^5
- s consists only of the characters '.', 'T', and 'C'
- Each move shifts a token exactly +3; a token cannot move off the board or onto another token
- A coin is collected only when a token lands on its cell, and each coin is collected at most once
Examples
Input: ("T..C",)
Expected Output: 1
Explanation: Token at 0 moves to 3 (a coin), collecting it. Positions 0 and 3 share residue 0 mod 3. Answer: 1.
Input: ("T..C..C",)
Expected Output: 2
Explanation: Residue 0: cells 0(T),3(C),6(C). The token sweeps 0->3->6, landing on both coins. Answer: 2.
Hints
- Every move changes a token's index by exactly +3, so a token can only ever reach cells with the same value of (index mod 3). Coins are therefore reachable only by tokens in the same residue class — split the board into three independent sub-problems.
- Within one residue class, a token sweeping right lands on every cell it passes, so moving it further right can only collect more coins. The only limit is that a token cannot land on another token, so tokens keep their relative order.
- Process the tokens of a residue class from rightmost to leftmost: the rightmost may sweep to the last cell of its residue, and each subsequent (more-left) token may sweep up to just before where the token on its right stopped. Count the distinct coins covered.