Define \(\operatorname{dp} _ i[H]\ (H\in\lbrace\)R, P, S\(\rbrace)\) by:

• \(\operatorname{dp} _ i[H]\coloneqq\) the maximum number of Takahashi’s wins during conforming first \(i\) hands of Takahashi such that his \(i\)-th hand is \(H\).

Here, we define \(\operatorname{dp} _ 0[H]=0\) for convenience. (DP stands for Dynamic Programming.)

Takahashi’s \(i\)-th move is solely dependent on Aoki’s \(i\)-th hand and Takahashi’s \(i\)-th hand.

Therefore, \(\operatorname{dp} _ i[H]\ (H\in\lbrace\)R, P, S\(\rbrace)\) can be found based on \(\operatorname{dp} _ {i-1}\ (H\in\lbrace\)R, P, S\(\rbrace)\) (and the value \(S _ i\)).

Specifically, let \(\operatorname{rps}(a,b)\) be \(1\) if \(a\) wins \(b\), \(-1\) if it loses, and \(0\) if they are draw (here rps stands for rock-scissors-paper), then

\[\operatorname{dp} _ i[H]=\begin{cases}\displaystyle\max _ {H^\prime\neq H}\operatorname{dp} _ {i-1}[H^\prime]&\ &(\operatorname{janken}(H,S _ i)=0)\\1+\displaystyle\max _ {H^\prime\neq H}\operatorname{dp} _ {i-1}[H^\prime]&&(\operatorname{janken}(H,S _ i)=1)\\0&&(\operatorname{janken}(H,S _ i)=-1).\end{cases}\]

While we may set \(-\infty\) to the value of the DP table when losing, one can prove that setting \(0\) still yields a correct value.

The following is sample code.

#include <iostream>
#include <array>
#include <algorithm>

int main() {
    using namespace std;
    unsigned N;
    cin >> N;
    string S;
    cin >> S;

    array<unsigned, 3> dp{};
    auto&& [rock, scissors, paper]{dp};

    for(const auto c : S){
        // Moves are limited to those not equal to the previous one
        dp = {max(scissors, paper), max(rock, paper), max(rock, scissors)};
        // Losing move must not be made = maximum winning count is 0
        // Making winning move increases the maximum value +1
        if (c == 'R') {
            scissors = 0;
            ++paper;
        } else if (c == 'S') {
            paper = 0;
            ++rock;
        } else if (c == 'P') {
            rock = 0;
            ++scissors;
        }
    }

    cout << ranges::max(dp) << endl;

    return 0;
}