Official Analysis (C++)

Video Solution

Note: The video solution might not be the same as other solutions. Code in C++.

Solution

The main observation for this problem is that we only need to keep track of the number of games played $i$, the number of times switched so far $j$, and the current gesture $k$ in order to determine the largest number of previous games won for any game $i$.

For every move, either Bessie can either switch or stay on her current gesture. If she changes her gesture, then the next game $i+1$ will have used $j+1$ gestures, which corresponds to the $\texttt{dp}$ state $\texttt{dp}[i+1][j+1][k]$. We can simulate this for all 3 gestures. Then, we just increment $\texttt{dp}[i][j][k]$ if Bessie wins at game $i$ with gesture $k$.

Note that you can just compare the current gesture to H, P, S because there is always exactly one way to win.

Time Complexity: $\mathcal{O}(NK)$

Copy
with open("hps.in") as read:
	n, k = map(int, read.readline().strip().split())
	moves = [0] * n
	for i in range(n):
		a = read.readline().strip()
		if a == "H":
			moves[i] = 0
		elif a == "P":
			moves[i] = 1
		else: