# Codeforces 814C An impassioned circulation of affection

The first thing to notice is that we are only changing other colours to Koyomi's favourite one. Furthermore, we won't create disconnected segments of that colour, for that's no better than painting just around the longest among them.

This leads us to a straightforward approach: when faced with a query (m, c), we check each segment [l, r] and determine whether it's possible to fill this segment with letter c, within at most m replacements. This can be done by finding the number of times c occurs in that segment (denote it by tc), and checking whether (r - l + 1) - t ≤ m. But this O(n2·q) solution would be too slow.

Since the number of different queries is 26n, we can calculate all answers beforehand. For each letter c and a segment [l, r], we'll be able to fill the whole segment with c within (r - l + 1) - tc moves. Use this information to update the answers, and employing a "prefix max" method gives us a time complexity of O(n2·|Σ| + q), where |Σ| equals 26. Refer to the code for a possible implementation.

Bonus. Find out the O(n2  +  n·|Σ|  +  q) solutions and the O(nq) solutions (some of them may get TLE — remember to check against maximum data next time!).

#include <bits/stdc++.h>
using namespace std;
template<typename T>
x=0;int _f=0;char ch=getchar();
while(ch<'0'||ch>'9')_f|=(ch=='-'),ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x=_f?-x:x;
}
int n,q;
char s[1500+5];
int cal(int k,const char *f);
int main(){
scanf("%s",s);
int k;
char f[2];
scanf("%d%s",&k,f);
printf("%d\n",cal(k,f));
}
return 0;
}

int cal(int k,const char *f){
int l,r;
l=r=0;
int ans=0,cnt=0;
while (l<n || r<n){
while (r<n && ((cnt<k) || (s[r]==f[0]))){
if (s[r]!=f[0]) cnt++;
r++;
}
ans=max(ans,r-l);
if (s[l]!=f[0]){
cnt--;
}
l++;
}
return ans;
}


#include <bits/stdc++.h>
using namespace std;
template
x=0;int _f=0;char ch=getchar();
while(ch<'0'||ch>'9')_f|=(ch=='-'),ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x=_f?-x:x;
}
int n,q;
char s[1500+5];
int ans[26][1500+5];
int main(){
scanf("%s",s);
for (int alp=0;alp<26;alp++){
for (int i=0;i<n;i++){
int cnt=0;
for (int j=i;j<n;j++){
if ((s[j]-'a')!=alp) cnt++;
ans[alp][cnt]=max(ans[alp][cnt],j-i+1);
}
}
for (int i=1;i<=n;i++){//因为题目要求改变字母数可以小于m，所以可以以此来更新ans[alp][i]的最大值
ans[alp][i]=max(ans[alp][i],ans[alp][i-1]);
}
}
}