Rock-Paper-Scissors Bot
Contest: Kotlin Heroes: Episode 11
Tags: *special, greedy, strings

Rock-Paper-Scissors is a game for two players. It is played in rounds. During each round, every player chooses one of three moves: Rock, Paper, or Scissors. Depending on the chosen moves, the following happens:

- if one player chooses Rock and the other player chooses Paper, the player who chooses Paper wins and gets a point;
- if one player chooses Scissors and the other player chooses Paper, the player who chooses Scissors wins and gets a point;
- if one player chooses Scissors and the other player chooses Rock, the player who chooses Rock wins and gets a point;
- and if both players choose the same move, nobody wins and nobody gets a point.

Monocarp decided to play against a bot. During the game, Monocarp noticed that the bot's behavior is very predictable:

- in the first round, it chooses Rock;
- in every round except the first, it chooses the move that beats the opponent's move in the previous round (for example, if in the previous round its opponent played Scissors, then the bot chooses Rock now).

Monocarp has a favorite string $$$s$$$, consisting of the characters R, P, and/or S. Monocarp decided to play a series of rounds against the bot. However, he wants both of the following conditions to be met:

- the final score is in favor of Monocarp (i. e., the number of rounds he won is strictly greater than the number of rounds the bot won);
- the string $$$s$$$ appears as a contiguous substring in the sequence of the bot's moves (where R denotes Rock, P denotes Paper, and S denotes Scissors).

Help Monocarp and calculate the minimum number of rounds he needs to play against the bot to satisfy both of the aforementioned conditions.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The only line of each test case contains a string $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$), consisting of the characters R, P, and/or S.

Additional constraint on the input: the sum of the lengths of the strings $$$s$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, print a single integer — the minimum number of rounds Monocarp needs to play against the bot to satisfy both of the aforementioned conditions.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the first example, Monocarp can play PPR, then the bot's moves are RSS, and the score is $$$2:1$$$ in favor of Monocarp.

In the second example, Monocarp can play P, then the bot's moves are R, and the score is $$$1:0$$$ in favor of Monocarp.

In the third example, Monocarp can play RPR, then the bot's moves are RPS, and the score is $$$1:0$$$ in favor of Monocarp.

In the fourth example, Monocarp can play RRRSPR, then the bot's moves are RPPPRS, and the score is $$$3:2$$$ in favor of Monocarp.

In the fifth example, Monocarp can play PRRSPRS, then the bot's moves are RSPPRSP, and the score is $$$6:1$$$ in favor of Monocarp.

In the sixth example, Monocarp can play PRRRS, then the bot's moves are RSPPP, and the score is $$$3:2$$$ in favor of Monocarp.

In the seventh example, Monocarp can play RSR, then the bot's moves are RPR, and the score is $$$1:0$$$ in favor of Monocarp.

Example input:
7
SS
R
RPS
RPPP
SPPRSP
PPP
PR

Example output:
3
1
3
6
7
5
3

Editorial:
First of all, let's map the characters R, P and S to integers from $$$0$$$ to $$$2$$$ so that we can get who wins by subtracting them. For example, if we map R to $$$0$$$, P to $$$1$$$ and S to $$$2$$$, then between two moves $$$x$$$ and $$$y$$$, we can check who beats whom: if $$$(y - x) \equiv 1 (\mod 3)$$$, then $$$y$$$ beats $$$x$$$, and if $$$(y - x) \equiv 2 (\mod 3)$$$, then $$$x$$$ beats $$$y$$$. This is an easy way to get which move beats which, and we can also obtain the move which beats move $$$x$$$ by computing $$$(x+1) \bmod 3$$$ (or the move which is beaten by $$$x$$$ as $$$(x+2) \bmod 3$$$).
Now, let us consider the string of bot's moves. We will try to "expand" it to the left and/or right so that it meets the conditions from the statement. If its length is denoted by $$$n$$$, then the results of $$$n-1$$$ rounds are determined by this string (all rounds except for the last round, since we can play anything we want in the last round, but our moves in all other rounds are described by bot's moves in the next rounds). Let's calculate how many rounds from these $$$n-1$$$ rounds we win. Also, we can consider that we win in the last round, since we can play anything we want.
If our score is not big enough, we can "fix" it by appending additional characters to the right end of the bot's string. We can always choose such a character to increase our score by $$$1$$$. For example, if the last character in the bot's string is R, then if we use P in the last round, the bot will respond with S in the next round (and we can use R to beat it). So, if the last character is R, we append S; if the last character is S, we append P, and so on — and it increases our score by $$$1$$$ every time we append one character. We don't even have to actually append characters, we can simply calculate the number of characters we need so that our score is higher.
However, there is still one problem to solve: what if the bot's string does not begin with R? Then we must append several characters at the beginning.
One possible solution to this issue does as follows: choose a small constant $$$K$$$, consider all strings of no more than $$$K$$$ characters that begin with R, and try to append them to the beginning of the given string $$$s$$$; then consider only the possibility of appending characters to the right end of the string we got. Let's prove that $$$K=2$$$ is enough (and also design a simpler solution):
• if the starting character in the bot's string is R, then there is no issue;
• if the starting character in the bot's string is S, it means we played a P in the previous move. Let's add R to the start of the bot's string and play P in the first round; this both increases our score by $$$1$$$ and "fixes" the issue;
• but if the starting character in the bot's string is P, it gets a bit trickier. We can either add R to the beginning right away, but this means we played R in the first round, so we got a tie (we increased the length by $$$1$$$, but the score is still the same). But sometimes it's better to add RS in the beginning of bot's string — this will increase our score by $$$2$$$.
This way, we get a solution working in $$$O(n)$$$: try to add R or RS to the beginning of the bot's string if it does not begin with R, and calculate the minimum number of rounds we need to add at the end.