TopCoder problem "TheStringGame" used in SRM 428 (Division I Level Three)

Problem Statement


John and Brus are playing a game where they alternate moves and John goes first. Initially, there is a string that contains only uppercase letters 'X', 'O' and 'L'. A move consists of replacing a single occurrence of 'X' with either 'O' or 'L'. After a player moves, if "LOL" (quotes for clarity) appears as a substring, that player immediately wins and the game ends. Otherwise, the game continues until there are no more 'X's left.

Both players use an optimal game strategy. If a player can win, he will follow the strategy that minimizes the number of moves in the game. Otherwise, if a player can make the game end without a winner, he will follow the strategy that does so (note that in this case the total number of moves in the game does not depend on the chosen strategy). Otherwise, if a player cannot win and cannot end the game in a draw, he will follow the strategy that maximizes the number of moves in the game.

You are given a String s containing the initial state of the game. If the game will end without a winner, return "Draw". If John will win the game, return "John x", and if Brus will win the game, return "Brus x", where x is the number of moves in the game, with no leading zeroes (all quotes for clarity).



Method signature:String winner(String s)
(be sure your method is public)


-s will contain between 1 and 16 characters, inclusive.
-Each character of s will be 'X', 'O' or 'L'.
-s will not contain "LOL" as a substring.


Returns: "John 1"
John can win by changing the 'X' between the two 'L's into a 'O'.
Returns: "Brus 2"
Brus can win this game after John's first move, regardless of what John does.
Returns: "Draw"
No moves available.
Returns: "Brus 16"

Problem url:

Problem stats url:




PabloGilberto , Olexiy , ivan_metelsky

Problem categories:

Encryption/Compression, String Parsing