If we were to simulate Bessie's gameplay against FJ with brute force, we would need to keep track of how many games Bessie has played and won so far, Bessie's current gesture, and how many more times Bessie can switch gestures. This approach is far too slow when $N$ gets large, since there are at least $2^K \cdot \binom{N}{K}$ different ways Bessie can choose to switch gestures.

However, if we look at the information we have to keep track of, we note that the number of games Bessie has played is at most $N$, and the number of times Bessie can still switch gestures is at most $K$. If we memoise the maximum number of games Bessie can win, we only consider at most $O(NK)$ states, each with at most 3 transitions, for an $O(NK)$ dynamic programming solution.

Here is Travis Hance's solution.

#include <cstdio>
#include <cassert>
#include <algorithm>
using namespace std;

#define NMAX 100000
#define KMAX 20

int moves[NMAX];

int dp[NMAX + 1][KMAX + 1][3];

int main() {
    int n, k;
    scanf("%d", &n);
    scanf("%d", &k);

    char s[10];
    for (int i = 0; i < n; i++) {
        scanf("%s", s);
        if (s[0] == 'H') moves[i] = 0;
        if (s[0] == 'P') moves[i] = 1;
        if (s[0] == 'S') moves[i] = 2;
    }

    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            for (int state = 0; state < 3; state++) {
                if (i == 0) {
                    dp[i][j][state] = 0;
                } else {
                    if (j == 0) {
                        dp[i][j][state] = dp[i-1][j][state] + (moves[i-1] == state ? 1 : 0);
                    } else {
                        int ostate1 = (state + 1) % 3;
                        int ostate2 = (state + 2) % 3;
                        dp[i][j][state] = max(max(dp[i-1][j][state], dp[i-1][j-1][ostate1]), dp[i-1][j-1][ostate2]) + (moves[i-1] == state ? 1 : 0);
                    }
                }
            }
        }
    }

    printf("%d\n", max(max(dp[n][k][0], dp[n][k][1]), dp[n][k][2]));
}