Maximum Coins With Moving Tokens
Learn this problem
GoogleINTERNOAProblem statement
There is a single-player board game with N positions described by a string board. Each position is empty ('.'), contains a player's token ('T'), or contains a coin ('C'). The player may have multiple tokens.
A coin is collected when a token is placed on the coin's position. Each coin can be collected only once.
In one turn, the player may move one token exactly three positions to the right. The token does not stop on the positions in between, and every token may be moved multiple times. A token cannot be moved if another token already occupies its destination.
Return the maximum number of coins the player can collect.
Implement solution(board), where board is a string of length N.
Function
solution(board: String) → intExamples
Example 1
board = "TT.T.CCCCC"return = 3The 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 = 1Example 3
board = "C..TT.CT.C"return = 2Constraints
Nis an integer within the range[1..100].- String
boardconsists only of the characters'.','T'and/or'C'.