笔试刷题-头条

思路如下：

由于只有两个字符，就找其中一个字符来变，另一个也变，看最后可以组成的最长字符串

维护两个列表去记录两个字符分别在字符串出现的下标

以上述例子为例：

a_pos = {0,1,2,4,5,7,8,9}

其中0是和长度+1的9分别表示端点方便计算而已

在把a_pos中找M个变换（不找端点变换），貌似一看暴力要2^M其实不是，做一个暴力枚举从a_pos找出第一个startIdx（a_pos的下标），到startIdx+M-1个变换成b肯定就是，以startIdx变换a可以变到的最长连续序列，然后暴力枚举即可，但是若M大于a_pos的长度，也就是说把a可以全部变b那么直接返回N即可

代码如下：

#include<stdio.h>
#include<iostream>
#include<vector>
#include<string>

using namespace std;

int main()
{
    int N, M;
    string str;
    vector<int> a_pos_vec, b_pos_vec;
    cin>>N>>M;
    getchar();
    cin>>str;
    a_pos_vec.push_back(0);
    b_pos_vec.push_back(0);
    for(int cur=1; cur<=N; cur++)
    {
        if(str[cur-1]=='a')
        {
            a_pos_vec.push_back(cur);
        }
        else if(str[cur-1]=='b')
        {
            b_pos_vec.push_back(cur);
        }
        else
        {
            return -1;
        }
    }
    a_pos_vec.push_back(N+1);
    b_pos_vec.push_back(N+1);

    int res=-1;
    if(a_pos_vec.size()-2<M)
    {
        res = max(res, N);
    }
    else
    {
        for(int cur=1; cur+M-1<a_pos_vec.size()-1; cur++)
        {
            int startCur = cur;
            int endCur = startCur+M-1;
            int len = a_pos_vec[endCur+1]-a_pos_vec[startCur-1]-1;
            res = max(res, len);
        }
    }
    if(b_pos_vec.size()-2<M)
    {
        res = max(res, N);
    }
    else
    {
        for(int cur=1; cur+M-1<b_pos_vec.size()-1; cur++)
        {
            int startCur = cur;
            int endCur = startCur+M-1;
            int len = b_pos_vec[endCur+1]-b_pos_vec[startCur-1]-1;
            res = max(res, len);
        }
    }
    cout<<res;
    return 0;
}