しゃくとり法

// しゃくとり法
// 条件を満たす連続した区間の最長のものをO(N)で求める。
// 考え方なので本来テンプレにはできないが、
// いざ組もうとするとバグがでるので見本を載せておきました。

// サンプル
// '0'と'1'からなる文字列より'1'が連続する最長連続区間の長さを求める。
// "011"なら2、"1100111110"なら5。

string s = "1100111110";

ll index1 = -1;
ll index2 = 0;
ll d[2] = {0,0};
ll mx = 0;
while(1){
  if(index1==s.sz)break;
  if(index2==s.sz)break;
  if(d[0]>0){
    if(s[index2]=='0')d[0]--;
    else d[1]--;
    index2++;
  }
  else{
    index1++;
    if(s[index1]=='0')d[0]++;
    else d[1]++;
  }
  mx = max(mx,index1-index2);
}

cout << mx << endl;