Codeforces #354 Div2 C. Vasya and String

最近しょうもないミスが多いな…。
http://codeforces.com/contest/676/problem/C

問題

N文字のabだけで構成された文字列Sがある。
S中最大K文字だけ内容を置き換えられるとき、同じ文字だけで構成される連続部分文字列は最長何文字か。

解法

a,bの登場回数の累積和を取り、尺取法かDPのどちらかでa,bそれぞれの登場回数がK回少ない位置の左端を計算すれば、各文字を右端とする題意を満たす最長部分文字列が得られる。
後はその最大値を答えればよい。

string S;
int N,K;

int lef[2][202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	memset(lef,0x3f,sizeof(lef));
	
	cin>>N>>K;
	cin>>S;
	int ma=1,a=0,b=0;
	lef[0][0]=lef[1][0]=-1;
	FOR(i,N) {
		if(S[i]=='a') lef[0][++a]=i;
		else lef[1][++b]=i;
		ma=max(ma,i+1-(lef[0][max(a-K,0)]+1));
		ma=max(ma,i+1-(lef[1][max(b-K,0)]+1));
	}
	cout<<ma<<endl;
	
	
}

まとめ

26種類の文字を使っても良かった問題かもね。