首页 > itarticle > 翻转连续最长子序列

翻转连续最长子序列

admin 11月 14, 2020 0

题目描述

有一个仅包含a和b两种字符的字符串s，长度为n，每次操作可以把一个字符做一次转换（把一个a设置为b，或者把一个b置成a)；但是操作的次数有上限m，问在有限的操作数范围内，能够得到最大连续的相同字符的子串的长度是多少。

输入描述

第一行两个整数 n , m (1<=m<=n<=50000)，第二行为长度为n且只包含a和b的字符串s。

输出描述

输出在操作次数不超过 m 的情况下，能够得到的最大连续全a子串或全b子串的长度。

示例

输入

1 2	8 1 aabaabaa

输出

分析(以翻转a为例)

翻转的操作次数为m，如果可以找出包含m个a的最长连续子串，然后将m个a翻转，即为本题的答案。
将a的下标组成新的数组array,则包含m个a连续序列的长度为 array[i+m]-array[i-1]-1;
如果这m个a中包含序列中的第一个或者最后一个a，那么，连续序列的长度为 array[i+m]-array[i-1];

代码如下：


#include<string>
using namespace std;
const int maxn=50040;
void (string str,int k)  
{
    int len=str.length();
    int arraya[maxn]={0};      //字符串中所有元素'a'的下标组成的数列 
    int arrayb[maxn]={0};      //字符串中所有元素'b'的下标组成的数列 
    int J=1;                   //计数符 
    int K=1;
    int maxa=0;                //记录最大长度 
    int maxb=0;
    for(int i=0;i<len;i++)     //遍历字符串，生成目标数组 
    {
        if(str[i]=='a')
        {
            arraya[J++]=i+1;
        }
        if(str[i]=='b')
        {
             arrayb[K++]=i+1;
        }
    }                
    arraya[J]=len;           //添加首末元素 
    arrayb[K]=len;
    arraya[0]=1;
    arrayb[0]=1;
    int temp1,temp2;         //记录每一个遍历的连续字符串长度 
    for(int i=1;i<=J-k;i++)
    {
        if(i==1 || i==J-k)     //如果要反转的字符在第一个或者最后一个 
        {
            temp1=arraya[i+k]-arraya[i-1];  //不需要减去1 
        }
        else
        {
            temp1=arraya[i+k]-arraya[i-1]-1;  //否则需要减去1 
        }
        if(temp1>maxa)
        {
            maxa=temp1;           //将最大值保存 
        }
    }
    for(int i=1;i<=K-k;i++)
    {
        if(i==1 || i==K-k)
        {
             temp2=arrayb[i+k]-arrayb[i-1];
        }
        else
        {
             temp2=arrayb[i+k]-arrayb[i-1]-1;
        }
        if(temp2>maxb)
        {
            maxb=temp2;
        }
    }
    int a=(maxa>maxb)?maxa:maxb;   //找出翻转a和b中最长的序列 
    cout<<a<<endl;
    
}
int main()
{
    string str;
    int n,m;
    while(cin>>n>>m)
    {
        cin>>str;
        int len=str.length();
        longstr(str,m);
    }
}