P6120 [USACO17JAN] Hoof, Paper, Scissor S

*This problem has the same meaning as the [Gold problem with the same name](/problem/P3609). The only difference is the limit on the number of times you can change gestures.*

You may have played “Rock, Paper, Scissors”. This game is also popular among cows, but its name becomes “Hoof, Scissors, Paper”. The rules of “Hoof, Scissors, Paper” are very similar to “Rock, Paper, Scissors”. Two cows count to three, then each shows a gesture representing hoof, scissors, or paper. Hoof beats scissors, scissors beats paper, and paper beats hoof. In particular, if both cows show the same gesture, it is a tie. Now FJ and Bessie will play $N$ rounds. Bessie has already predicted what gesture FJ will play in each round. However, Bessie is lazy: she wants to change her gesture at most once. Please help Bessie find the maximum number of rounds she can win.

The first line contains an integer $N$ ($1 \leq N \leq 10^5$). The next $N$ lines each contain one letter representing FJ’s gesture in that round. `H` means Hoof, `S` means Scissors, and `P` means Paper.

Output one integer, representing the maximum number of rounds Bessie can win under the condition that she changes her gesture at most once.

Translated by ChatGPT 5