P3609 [USACO17JAN] Hoof, Paper, Scissors G

*This problem has the same statement as the [problem with the same name in the Silver division](/problem/P6120). The only difference is the limit on how many times the gesture can be changed.*

You might have played “Rock, Paper, Scissors.” This game is also popular among cows, but it is called “Hoof, Scissors, Paper.” The rules of “Hoof, Scissors, Paper” are very similar to “Rock, Paper, Scissors.” Two cows count to three, then show one of the gestures representing hoof, scissors, or paper. Hoof beats scissors, scissors beat 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 FJ’s gesture in each round. However, Bessie is lazy and wants to change her gesture at most $K$ times. Please help Bessie determine the maximum number of rounds she can win.

The first line contains two integers $N,K$ ($1 \leq N \leq 10^5$, $0 \leq K \leq 20$). The next $N$ lines each contain one letter, representing FJ’s gesture in that round. `H` stands for hoof (Hoof), `S` stands for scissors (Scissors), and `P` stands for paper (Paper).

Output a single integer, the maximum number of rounds Bessie can win if she can change her gesture at most $K$ times.

Translated by ChatGPT 5