Compute max coins with 3-step token moves

Q: Compute max coins with 3-step token moves

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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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:

A move selects one token and moves it exactly 3 positions to the right (from index i to i+3 ).
A token cannot move if i+3 is outside the board.
A token cannot land on a cell currently occupied by another token ( T ).
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).

Compute max coins with 3-step token moves

Overview

Comments (0)