import java.util.*;
import java.io.*;
public class miners {
public static void main(String[] args) throws IOException{
BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(new PrintStream(System.out));
n=Integer.parseInt(f.readLine());
char[]atem=f.readLine().toCharArray();
arr=new int[n];
for(int i=0;i<n;i++){
if(atem[i]=='M'){
arr[i]=1;
}
else if(atem[i]=='F'){
arr[i]=2;
}
else{
arr[i]=3;
}
}
int dp[][][][][][]=new int[2][4][4][4][4][2];
// dp[0][0][0][0][0][0]=arr[0];
// dp[0][0][0][0][0][1]=arr[0];
dp[1][0][arr[0]][0][0][0]=1+(arr[0]==arr[1]?1:2);
dp[1][0][arr[0]][0][0][1]=2;
dp[1][0][0][0][arr[0]][0]=2;
dp[1][0][0][0][arr[0]][1]=1+(arr[0]==arr[1]?1:2);
for(int y=1;y<n-1;y++){
int i=y%2;
int t=(i+1)%2;
for(int j=0;j<4;j++){
for(int k=0;k<4;k++){
for(int p=0;p<4;p++){
for(int d=0;d<4;d++){
for(int u=0;u<2;u++){
if(dp[i][j][k][p][d][u]!=0){
int a=dp[t][j][k][d][arr[y]][1];
int b=dp[t][k][arr[y]][p][d][0];
int c= dp[t][k][arr[y]][p][d][1];
int r=dp[t][j][k][d][arr[y]][0];
if(u==0){
dp[t][k][arr[y]][p][d][0]=Math.max(b,dp[i][j][k][p][d][u]+numEqual(k,arr[y],arr[y+1]));
dp[t][k][arr[y]][p][d][1]=Math.max(c,dp[i][j][k][p][d][u]+numEqual(p,d,arr[y+1]));
}
if(u==1){
dp[t][j][k][d][arr[y]][1]=Math.max(a,dp[i][j][k][p][d][u]+numEqual(d,arr[y],arr[y+1]));
dp[t][j][k][d][arr[y]][0]=Math.max(r,dp[i][j][k][p][d][u]+numEqual(j,k,arr[y+1]));
}
// if(dp[2][0][1][0][3][1]==5)
// i=i;
}
}
}
}
}
}
for(int j=0;j<4;j++){
for(int k=0;k<4;k++){
for(int p=0;p<4;p++){
for(int d=0;d<4;d++){
for(int u=0;u<2;u++) {
dp[i][j][k][p][d][u]=0;
}
}
}
}
}
}
// for(int i=0;i<n;i++){
// for(int q=0;q<4;q++)
// }
int ans=0;
for(int j=0;j<4;j++){
for(int k=0;k<4;k++){
for(int p=0;p<4;p++){
for(int d=0;d<4;d++){
for(int u=0;u<2;u++){
if(dp[(n-1)%2][j][k][p][d][u]>ans){
j=j;
}
ans=Math.max(ans,dp[(n-1)%2][j][k][p][d][u]);
}
}
}
}
}// ans=1+recurse(0,0,0,arr[0],0,0,0);
// int b=1+recurse(0,0,0,0,0,0,arr[0]);
// System.out.print(Math.max(ans,b));
System.out.print(ans);
f.close();
out.close();
}
static int n;
static int[]arr;
// static int [][][][][][][]dp=new int[100002][4][4][4][4][4][4];
static int recurse(int idx,int l1,int l2,int l3,int r1, int r2,int r3){
int max=0;
if(idx==-1+n)return 0;
//choose left
int val=numEqual(l2,l3,arr[idx+1]);
val+=recurse(idx+1,l2,l3,arr[idx+1],r1,r2,r3);
max=Math.max(max,val);
val=numEqual(r2,r3,arr[idx+1]);
val+=recurse(idx+1,l1,l2,l3,r2,r3,arr[idx+1]);
max=Math.max(max,val);
return max;
}
static int numEqual(int a, int b, int c){
if(a==0 && b==0 && c==0)return 0;
if(a==0 && b==0)return 1;
if(a==0){
return b==c?1:2;
}
if(a==b && b==c)
return 1;
if(a==b)
return 2;
if(b==c)
return 2;
if(a==c)return 2;
return 3;
}
}
class pair implements Comparable <pair>{
int num;
int idx;
public int compareTo(pair other){
return num- other.num;
}
pair(int a, int b)
{
num=a;
idx=b;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
91 ms |
9732 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
90 ms |
9776 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
90 ms |
9860 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
88 ms |
9748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
88 ms |
9704 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
94 ms |
9576 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
136 ms |
11156 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
295 ms |
15544 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
377 ms |
16804 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
494 ms |
16084 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
824 ms |
17360 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1187 ms |
18136 KB |
Output is correct |
