Reformulation

We have a string S of length N over three letters H, P, S and we want
to find the string S' of length N that is the closest (in hamming
distance) to S and such that S' is made of K+1 chunks each chunk using
only one letter.
====

By doing some examples or simplification we can see that when K=0
(i.e. no change) the maximal number of matchs won is easy to compute,
we just need to compute the number of each letter in the string.

Let us note m(S) the number of matches won by always playing the same move.

====
Dynamic problem

q(S,K) = what is the number of games of S I can win knowing that I can change K times


One possible recursion where we look at all possible places to cut S:

    q(S,K) =  min_{S1 S2 = S, i} q(S1,i) q(S2,K-i-1)

A better recursion is to look only at the first place where we change:


q(S,K) = min_{S1,S2} q(S1,K-1) + m(S2) where m(S)

Now if we look at the different argument we give to q we see that they
are all of the form q( M1 ... Mi, k) where 0\leq k \leq K and M1 ... Mi
is a prefix of the input string. Therefore our recursion can be replaced
with q(i,k) but that is not good enough as there are O(N×K) states and
O(N) transitions per state. We need to do better.

====

A more complex situation we can look at is to fix what is the first move,
i.e.

q(S,K,C) = what is the maximum number of games I can win knowning
         that I am currently playing C and that I can change K times?

now the recursion becomes something like:

q(S1 ... Sn,K,C) = min (min_C' q(S1...Sn, K-1,C')) (q(S2 ... Sn,K,C)+win(S1,C))


That is, either we continue playing the move C and we win q(S2 ... Sn,K,C)+win(S1,C)
where win(S1,C) is 1 when it wins and 0 otherwise, or we can change our move to C'
but we loose one move.

The number of states is N×K×3 and the number of transition per state is 4. That is OK.