How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a easy difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Compute max coins with 3-step token moves

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Take-home Project

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.

Input: ("T..CT..C",)

Expected Output: 2

Explanation: Two tokens (indices 0 and 4) in different residue classes; each reaches one coin (at 3 and 7 respectively). Answer: 2.

Input: ("TC.TC.TC",)

Expected Output: 0

Explanation: Every coin sits one cell to the right of a token (residue offset 1 apart), so no token can ever land on a coin. Answer: 0.

Input: ("T.C",)

Expected Output: 0

Explanation: The coin at index 2 has residue 2; the token at index 0 has residue 0 and can only reach 0,3,6,... — it can never reach the coin. Answer: 0.

Input: ("C..T",)

Expected Output: 0

Explanation: The only coin is to the LEFT of the token; tokens only move right, so it is unreachable. Answer: 0.

Input: ("",)

Expected Output: 0

Explanation: Empty board — no tokens, no coins. Answer: 0.

Input: ("C",)

Expected Output: 0

Explanation: A coin with no token to collect it. Answer: 0.

Input: ("...C..C..C",)

Expected Output: 0

Explanation: No tokens on the board, so nothing can be collected. Answer: 0.

Input: ("T.....C.....C",)

Expected Output: 2

Explanation: Residue 0: cells 0(T),6(C),12(C). The token sweeps through both coins. Answer: 2.

Input: ("T..C..C..C",)

Expected Output: 3

Explanation: Residue 0: 0(T),3(C),6(C),9(C). One token sweeps right, collecting all three coins. Answer: 3.

Input: ("T..T..C..C",)

Expected Output: 2

Explanation: Residue 0: 0(T),3(T),6(C),9(C). The right token goes 3->6->9 collecting both coins (the left token at 0 cannot pass it but isn't needed). 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.

Quick Overview

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.