(Analysis by Nick Wu)

The text of the problem gives us a fairly simple algorithm to implement - try every possible combination of picking one move for the first $x$ moves and picking another move for the other $N-x$ moves. $x$ can take on $N+1$ values, so there are at most $9(N+1)$ different combinations to try, which is small enough that we could try all of them.

If we directly simulate trying out all combinations, it will take linear time to simulate a single one, giving us an $O(N^2)$ algorithm which is too slow.

If we look carefully at the linear-time simulation, we're doing the same thing repeatedly - namely, taking a prefix of the list and counting how many items in the prefix take on a specific value, and doing the same for the suffix. If we were able to efficiently precompute, for every prefix, how many items in that prefix take on that value, then it would take constant time to simulate a single combination and our algorithm would be fast enough!

The key to note about precomputing the values quickly is that any given prefix of a list is just a smaller prefix of the list plus a single element. Therefore, if we precompute the desired values for the prefixes in increasing order of length of prefix, then we can compute all the values in linear time.

import java.io.*;
import java.util.*;
public class hps {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("hps.in"));
		PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("hps.out")));
		int n = Integer.parseInt(br.readLine());
		int[] l = new int[n];
		int[] lReverse = new int[n];
		for(int i = 0; i < n; i++) {
			String s = br.readLine();
			if(s.equals("P")) l[i] = 1;
			else if(s.equals("S")) l[i] = 2;
			lReverse[l.length-1-i] = l[i];
		int[][] matchPrefix = getMatch(l);
		int[][] matchSuffix = getMatch(lReverse);
		int ret = 0;
		for(int a = 0; a <= n; a++) {
			for(int i = 0; i < 3; i++) {
				for(int j = 0; j < 3; j++) {
					ret = Math.max(ret, matchPrefix[i][a] + matchSuffix[j][n-a]);
	public static int[][] getMatch(int[] l) {
		int[][] matches = new int[3][l.length+1];
		for(int i = 0; i < l.length; i++) {
			for(int j = 0; j < 3; j++) {
				matches[j][i+1] = matches[j][i];
		return matches;