AnotherTokenGame

Lucas and Greg are playing a board game. The board consists of n spaces in a line. Initially, each space is either empty (denoted '.'), or contains a single lime-colored token (denoted 'L'). All lime-colored tokens are owned by Lucas. This state of the board is described by the input you are given: the String s.

Next, Greg will choose a non-negative integer k not exceeding the number of empty spaces. He will then receive k gray tokens (denoted 'G') which he can distribute among k empty spaces of the board. Each empty space can hold at most one token. All gray tokens are owned by Greg.

Once Greg finishes placing his gray tokens, the actual game starts. In the game Lucas and Greg take alternating turns, with Lucas going first. In each turn of the game the current player chooses a token of their color and moves it either one space to the left or one space to the right. (The destination space must be empty.) If there are no available moves, the current player loses.

In some cases the game can go on indefinitely. Greg would like to know the minimum value of k such that he can guarantee a win, assuming he places his k tokens optimally and then plays optimally. Return this value of k.