FastPrep
Problem · Dynamic Programming

Maximum Coins With Moving Tokens

Learn this problem
● MediumGoogleOA
See Google hiring insights

Problem statement

You are given a string board representing a row of cells. Each cell may contain a token 'T', a coin 'C', or be empty '.'.

In one move, the player may move one token exactly three positions to the right. If the token moves onto a coin, that coin is collected. A token cannot be moved if there is already another token in the position it would move onto.

What is the maximum number of coins the player can collect?

Write a function solution(board) that, given a string board of length N, returns the maximum number of coins the player can collect.

Source note: The screenshot is missing part of the question, but the examples are clear enough for practice. If you know the full original version, feel free to tell us; we'll update it when we find a clearer source. 🦤

Function

solution(board: String) → int

Examples

Example 1

board = "TT.T.CCCCC"return = 3

The player can move the third and second tokens twice, collecting three coins in total:

"TT.T.CCCCC" -> "TT...CTCCC" -> "TT...C.CCT" -> "T...TC.CCT" -> "T....C.TCT".

It is still possible to move the first token, but it cannot collect any coins.

Example 2

board = "T...CCCC"return = 1

Example 3

board = "C..TT.CT.C"return = 2

Constraints

  • N is an integer within the range [1..100].
  • String board consists only of the characters '.', 'T' and/or 'C'.

More Google problems

drafts saved locally
public int solution(String board) {
  // write your code here
}
board"TT.T.CCCCC"
expected3
checking account