Maximize coins with tokens moving by +3
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Take-home Project
You are given a 1D board represented by a string `s` of length `n`. Each character is one of:
- `'.'` — an empty cell
- `'C'` — a cell containing exactly one coin
- `'T'` — a cell containing one of the player's tokens (there may be several tokens)
The player controls all tokens. Movement and scoring work as follows:
- A token may be moved any number of times, in any order.
- A single move sends a token **exactly 3 cells to the right**: from index `i` to index `i + 3`. No other distance is allowed, and tokens may never move left.
- A move is **invalid** if the destination cell is currently occupied by another token. A move that would land past the end of the board is also invalid (tokens never leave the board).
- When a token **lands** on a cell containing an as-yet-uncollected coin, that coin is collected and then disappears. Each coin is collected at most once.
- Only the **landing** cell counts. Coins on cells a token passes "over" mid-flight are **not** collected — but note a single move advances 3 cells at once, so a token does not actually visit the two cells in between.
**Task:** Return the **maximum number of coins** the player can collect over any optimal sequence of moves.
```hint Where to start
A token at index $i$ can only ever sit on indices $i, i+3, i+6, \dots$ — every reachable cell has the **same index modulo 3**. What does that imply about which tokens and coins can possibly interact?
```
```hint Decompose
Partition the board by index $\bmod\ 3$ into three independent sub-boards. Solve each one in isolation and sum the results, because a token can never change its residue class or reach a cell in another class.
```
```hint Within one residue class
Collapse a residue class into a chain (its cells in left-to-right order). In the chain, "advance by one step" right-only. Because tokens move right-only and can't share a cell, they can never cross — their left-to-right order is fixed. What is the largest set of coins they can collectively land on?
```
### Constraints & Assumptions
- $1 \le n \le 100$.
- Each cell is exactly one of `'.'`, `'C'`, `'T'`; a coin and a token never start on the same cell, so no coin is "pre-collected."
- Tokens are interchangeable except for the rule that two tokens cannot occupy the same cell at the same time.
- The board is static apart from token moves; no new coins or tokens appear.
### Clarifying Questions to Ask
- Can two tokens occupy the same cell, even momentarily? (No — that makes the move invalid.)
- Is the order of moves across tokens free, or must each token finish before the next starts? (Moves may be freely interleaved.)
- Are coins consumed permanently once landed on, or can they regenerate? (Collected once, then gone.)
- Does a coin sitting under the cell a token *jumps over* get collected? (No — only the landing cell.)
- Can a token start on a coin? (No — input format guarantees one symbol per cell.)
### What a Strong Answer Covers
- **The mod-3 insight:** recognizing that a token's reachable cells share a residue class, so the board splits into three fully independent sub-problems whose answers sum.
- **Reduction within a class:** mapping each residue class to a left-to-right chain and arguing that right-only, non-crossing motion lets tokens collect every coin at or to the right of the **leftmost** token in that chain.
- **A correctness argument** that the collision constraint never blocks a reachable coin (e.g. a right-to-left serialization, or "the leftmost token alone could sweep the whole chain"), and that coins strictly left of every token are unreachable.
- **An $O(n)$ time, $O(1)$ space** implementation, plus edge cases: no tokens, no coins, multiple tokens per class, coins on both sides of a token, and small $n$.
- Awareness that naive framings (one global sweep ignoring mod 3, or a heavyweight matching/DP) are either wrong or unnecessary.
### Follow-up Questions
- How does the answer change if a move advanced by $k$ cells instead of 3? (The board splits into $k$ classes; everything else generalizes.)
- Suppose coins had **values** and you wanted to maximize total value rather than count — does the same greedy still hold?
- What if tokens could also move **left** by 3? How does reachability and the non-crossing argument change?
- If you additionally had to report *one* concrete optimal move sequence (not just the count), how would you construct it, and what is its length bound?
Quick Answer: This question evaluates proficiency in discrete optimization and state-space reasoning, emphasizing movement constraints, collision avoidance, modular-position effects from fixed-step moves (+3), and maximizing reward collection.
Solution
# Maximum coins collectible — solution
## Key insight: the +3 move splits the board into 3 independent chains
A token at index $i$ can only ever move to $i+3, i+6, \dots$, so over its entire lifetime it occupies only indices with the **same residue modulo 3** as its start, and only those to its right (motion is right-only, tokens never leave the board).
Two consequences:
- A token never changes its residue class, and it can never *land* on a cell of a different class.
- Therefore tokens and coins in residue class $r$ can never interact with anything in another class.
So the board partitions into **three completely independent sub-problems**, one per residue class $r \in \{0, 1, 2\}$, and
$$\text{answer} = \sum_{r=0}^{2} \text{(answer for class } r).$$
For each class, list its cells in left-to-right order to form a **chain**. In chain coordinates a move is simply "advance by one cell," right-only.
## Solving one chain
Index the chain cells $0, 1, 2, \dots$ left to right. Each cell holds a token (`T`), a coin (`C`), or nothing (`.`).
Two structural facts:
1. **No coins are skipped within a chain.** Advancing from chain position $p$ to $q$ lands on every cell in $(p, q]$ — adjacent chain cells are 3 apart on the real board, i.e. exactly one legal move — so a token sweeping rightward collects *every* coin it passes in chain coordinates.
2. **Tokens cannot cross.** Movement is right-only and two tokens can never share a cell, so the left-to-right order of tokens is invariant. The $k$-th token from the left always stays at or behind the $(k{+}1)$-th.
### Claim
> In a single chain, the collectible coins are **exactly** the coins at or to the right of the leftmost token. Let $t$ be the position of the leftmost token; every coin at chain position $> t$ is collectible, and no coin at position $< t$ is.
**Reachability of every coin right of $t$.** Process tokens **right-to-left**. The rightmost token sweeps to the end of the chain, collecting every coin from its start to the end. Then the next token to its left advances as far right as it needs to; the cell ahead is already vacated because the token in front has moved further right, so the "destination occupied" rule is never violated. Equivalently: ignore the other tokens and let the **leftmost token alone** walk to the end of the chain — it would land on every coin to its right, and the other tokens (all to its right, all able to step further right) only ever move out of its way. Either way no reachable coin is blocked. With $n \le 100$ there is ample room to serialize the moves.
**Coins left of $t$ are impossible.** No token ever moves left, so a coin strictly left of the leftmost token can never be landed on.
### Per-chain answer
Walk the chain left to right; once the first `T` is seen, count every subsequent `C`. A chain with no token contributes 0. (A token and coin never share a starting cell, so there is no "co-located coin" special case.)
## Final algorithm
For each residue class, scan its cells left to right and count coins seen after the first token; sum over the three classes.
```python
def max_coins(s: str) -> int:
total = 0
for r in range(3): # residue class 0, 1, 2
seen_token = False
for i in range(r, len(s), 3): # cells of this class, left -> right
ch = s[i]
if ch == 'T':
seen_token = True
elif ch == 'C' and seen_token:
total += 1
return total
```
- **Time:** $O(n)$ — every cell is visited once across the three passes.
- **Space:** $O(1)$.
## Worked examples
**`s = "T.C..C"`** (indices 0–5):
- Class $r=0$: cells $0, 3$ = `T`, `.` → token, no coin after → 0.
- Class $r=1$: cells $1, 4$ = `.`, `.` → 0.
- Class $r=2$: cells $2, 5$ = `C`, `C` → no token in this class → 0.
Answer **0**. The only token is at index 0 (class 0) and can reach just $0, 3$ — never the coins at 2 and 5, which live in class 2 with no token.
**`s = "T..C..C"`** (length 7):
- Class $r=0$: cells $0, 3, 6$ = `T`, `C`, `C` → token then two coins → 2.
Answer **2**. The single token sweeps $0 \to 3 \to 6$, landing on both coins.
## Edge cases
- **No tokens anywhere** → 0. **No coins** → 0.
- **Multiple tokens in one chain** → still "all coins right of the leftmost token"; the leftmost token determines reachability and the others only help or step aside.
- **Coins on both sides of a token** → coins left of the leftmost token are lost; all coins to its right are collected.
- **$n < 3$** → loops remain correct; classes with no cells contribute 0.
## Why other framings fail
- **One global sweep ignoring mod 3 over-counts:** a token can never reach a coin in a different residue class, so the three classes must be separated. That separation is the crux being tested.
- **Heavyweight matching / DP over tokens is unnecessary:** the collision constraint *looks* like it could force a token to miss a coin, but right-only motion plus non-crossing means the right-to-left serialization always succeeds. The greedy "every coin right of the leftmost token, per class" is exactly optimal — confirmed against brute-force search over all small boards.
## Addressing the follow-ups
- **Move of $k$ instead of 3:** identical structure with $k$ residue classes; the answer is the sum over classes of "coins right of the leftmost token." The code generalizes by replacing `3` with `k` and ranging `r` over `0..k-1`.
- **Valued coins, maximize total value:** the greedy still holds. Within a chain you can land on *every* cell at or right of the leftmost token, so you collect the full value of all coins in that reachable region — there is no trade-off to optimize. Per chain, sum the values of coins right of the leftmost token.
- **Tokens may also move left by 3:** reachability within a class becomes the *entire* class (a token can go either direction along its chain), so a class with at least one token can collect **all** of its coins. Non-crossing no longer holds, but it isn't needed — any single token can reach every cell in its chain. Per-chain answer becomes "all coins in the class if it has $\ge 1$ token, else 0."
- **Reporting a concrete optimal sequence:** use the right-to-left construction per chain — move the rightmost token to the chain end, then each next-left token to its target frontier. The total number of moves is bounded by the sum over tokens of their forward chain-distance, which is $O(n)$ per chain and $O(n)$ overall (each cell is stepped onto at most a constant number of times).