Maximize coins with tokens moving by +3

### Key observation: the +3 move splits the board into 3 independent chains A token can only move from `i` to `i + 3`. Repeating that, a token starting at index `i` can ever occupy only indices $$i,\; i+3,\; i+6,\; \dots$$ i.e. exactly the cells whose index has the **same residue modulo 3** as `i`, and only those **to its right** (moves are right-only and tokens never leave the board). So the board partitions into three completely independent sub-problems — one per residue class `r ∈ {0, 1, 2}`. Tokens in class `r` can never interact with tokens or coins in another class (a token never changes its index mod 3, and it can't land on a cell of a different class). **The answer is the sum of the answers for the three classes.** For each class, collapse its cells (in left-to-right order) into a 1D "chain." In chain coordinates a move is just "advance by one cell," right-only, and a cell may hold a token (`T`), a coin (`C`), or nothing (`.`). ### The within-chain rules Work entirely in one chain. Index the chain cells `0, 1, 2, …` left to right. - A token at chain position `p` can step to `p+1, p+2, …` (one cell per move). - Because every step lands on the very next chain cell, a token that advances from `p` to `q` **lands on every cell in `(p, q]`** — so it collects *every* coin sitting in that range (each coin once). Coins are not "jumped over" within the chain; consecutive chain cells are 3 apart on the real board, which is exactly one move. - Two tokens may never occupy the same cell **at the same time**. Right-only movement plus this rule means **tokens can never pass each other**: their left-to-right order is invariant. Token `k` (counting from the left) always stays at or behind token `k+1`. So the question reduces to: tokens keep their relative order, each token sweeps rightward, and collectively they want to land on as many coin cells as possible. ### Solving one chain Claim: **in a single chain you can collect every coin that lies at or to the right of the leftmost token.** Equivalently, let `t` be the position of the leftmost token in the chain; you collect all coins at positions `> t` (coins strictly left of every token are unreachable, since no token moves left). Why this is achievable without collisions: - The **rightmost** token sweeps to the end of the chain first, collecting every coin from its start to the end. Then the next token to its left sweeps up to (but not past) wherever it needs to, and so on. Process tokens **right-to-left**; each token only needs to advance into the region just vacated/owned by the token to its right, so the "destination occupied" rule is never violated — there is always a free cell to step onto because the token ahead has already moved further right (or to the same frontier minus one). With `n ≤ 100` there is ample room to serialize the moves. - A cleaner argument: a single token starting at the leftmost token position could, ignoring other tokens, walk the entire chain and pick up every coin to its right. Other tokens only sit to its right and can step out of its way (they too only move right). Therefore no coin at position `> t` is blocked. Why coins left of every token are impossible: tokens never move left, so any coin strictly to the left of the leftmost token can never be landed on. **Per-chain answer:** if the chain has at least one token at position `t_min` (leftmost token), count the coins at chain positions `> t_min`. If a chain has no token, it contributes `0`. (A token sitting *on* a starting coin: by the rules the coin is only collected when a token *lands* via a move, so a coin co-located with a token at the start is not pre-collected — but in this input format a cell is exactly one of `.`, `C`, `T`, so a token and a coin never share a starting cell. No special case needed.) ### Final algorithm For each residue class `r`, walk its cells left to right; once you have seen the first `T`, count every subsequent `C`. Sum across the three classes. ```python def max_coins(s: str) -> int: total = 0 for r in range(3): seen_token = False for i in range(r, len(s), 3): # cells of this residue 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)` — each cell is visited once across the three passes. - **Space:** `O(1)`. ### Worked example `s = "T.C..C"`, indices `0..5`. - Class `r=0`: cells at `0,3` → `s[0]='T'`, `s[3]='.'`. Token seen, no coin after → `0`. - Class `r=1`: cells at `1,4` → `'.'`, `'.'` → `0`. - Class `r=2`: cells at `2,5` → `'C'`, `'C'`. No token in this class → `0`. Answer `0`: the only token is in class 0 and there are no class-0 coins to its right; the two coins live in class 2 with no token. Correct — a token at index 0 can reach `0,3` only, never the `C`s at `2,5`. Now `s = "T..C..C"` (length 7): class `0` cells `0,3,6` = `'T','C','C'` → token then two coins → `2`. The single token sweeps `0→3→6`, landing on both coins. Answer `2`. ### Edge cases - **No tokens anywhere** → `0`. - **No coins** → `0`. - **Multiple tokens in one chain:** still just "all coins right of the leftmost token," because the leftmost token determines reachability and others only help / stay out of the way; they never block a reachable coin. - **Coins both left and right of a token:** left-of-leftmost-token coins are lost; right ones are all collectible. - **`n < 3`:** loops still correct; classes with no cells contribute `0`. ### Why simpler-looking approaches are wrong / unnecessary - This is *not* a bipartite-matching or DP-over-tokens problem. The collision constraint sounds like it could force a token to "miss" coins, but right-only motion plus non-crossing means the rightmost-first serialization always succeeds, so the greedy "everything right of the leftmost token, per class" is exactly optimal. - Treating the whole string as one sequence (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 the interviewer is testing.