codeforces1082/B(字符串中由相同字符组成的子字符串长度的处理,思维题）

B. Vova and Trophies

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

　　Vova has won $n$

The beauty of the arrangement is the length of the longest subsegment consisting of golden trophies. Vova wants to swap two trophies (not necessarily adjacent ones) to make the arrangement as beautiful as possible — that means, to maximize the length of the longest such subsegment.

Help Vova! Tell him the maximum possible beauty of the arrangement if he is allowed to do at most one swap.

Input

　　The first line contains one integer $n$

The second line contains $n$

Output　　

　　Print the maximum possible length of a subsegment of golden trophies, if Vova is allowed to do at most one swap.

Examples

Input

10
GGGSGGGSGG

Output

Input

4
GGGG

Output

Input

3
SSS

Output

Note

　　In the first example Vova has to swap trophies with indices $4$

　　In the second example Vova can make no swaps at all. The length of the longest subsegment of golden trophies in the sequence is $4$

　　In the third example Vova cannot do anything to make the length of the longest subsegment of golden trophies in the sequence greater than $0$

$0$

　　如样例1中可将第四个S与第九个G交换，得到的连续G字符串长度最长，长度为7。

$0$

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<map>
#include<string.h>
#include<cmath>
#include<string>
#define INF 0x3f3f3f3f

using namespace std;
int main()
{
    int n;
    while(cin>>n)
    {
        getchar();//前面是输入整数，后面是输入字符，所以吸收一个转行符 
        char a[100005];
        int sum[100005];
        cin>>a;
        memset(sum,0,sizeof(sum));
        sum[0]=0;
        int cnt=0;//计算每段的G个数 
        int k=1;//sum数组下标，从1开始并且sum[0]=0是为了遍历时方便计算GGGGG这种只有G的情况 
        int flag=0;//G的总个数 
        for(int i=0;i<n;i++)
        {
            if(a[i]=='G')
            {
                cnt++;
                flag++;
            }
            if(a[i]=='S'||i==n-1)//当结尾字符为G时也要将G的长度存入sum中 
            {
                sum[k++]=cnt;
                cnt=0;
            }
        }
        int ans=0;
        int Max=0;
        int flag3=0;
        for(int i=1;i<=k;i++)//遍历储存的每小段连续G的长度 
        {                        //分两种情况即可，1：两段中G长度和小于原字符串中G的数量，即有除两段之外的G来替换S
                                //                  2：两段中G长度和等于原字符串中G的数量，即没有除两段外的G来替换S 
            ans=sum[i]+sum[i-1];
            if(Max<ans+1&&flag>ans)//GGSGGSSG----情况1 /这要注意Max<ans+1而不是Max<ans,因为此情况得出的长度是ans+1 
            Max=ans+1;
            if(Max<ans&&flag==ans)//GGGGSGGGG----情况2 
            Max=ans;
        }
        cout<<Max<<endl;
    }
    return 0;
}

2019-01-192019-01-192019-01-19