Codeforces Round #418 (Div. 2) C. An impassioned circulation of affection(双指针)

题目链接：Codeforces Round #418 (Div. 2) C. An impassioned circulation of affection

题意：

给你一个字符串，有q个询问，每个询问一个x和一个字符 o。

现在让你在原来的字符串上最多改变x个字符，问能构成最长的o子串的长度。

题解：

一共有26*1500种状态，对于每个状态用双指针滚一滚就行了。

#include<bits/stdc++.h>
#define F(i,a,b) for(int i=(a);i<=(b);++i)
using namespace std;

const int N=1507;
int ans[27][N],n,k,x;
char s[N],o[2];

int del(int i,int j)
{
    int ans=0;
    for(int l=1,r=1,cnt=0;r<=n;r++)
    {
        cnt+=s[r]!=j;
        if(cnt<=i)ans=max(ans,r-l+1);
        while(l<=r&&cnt==i+1)cnt-=s[l]!=j,l++;
    }
    return ans;
}

int main(){
    scanf("%d%s",&n,s+1);
    F(i,1,n)s[i]-='a';
    F(i,0,25)F(j,1,n)ans[i][j]=del(j,i);
    scanf("%d",&k);
    while(k--)
    {
        scanf("%d%s",&x,o),o[0]-='a';
        printf("%d
",ans[*o][x]);
    }
    return 0;
}