Codeforces Round #354 (Div. 2) C. Vasya and String

High school student Vasya got a string of length n as a birthday present. This string consists of letters ‘a’ and ‘b’ only. Vasya denotes beauty of the string as the maximum length of a substring (consecutive subsequence) consisting of equal letters.

Vasya can change no more than k characters of the original string. What is the maximum beauty of the string he can achieve?

Input

The first line of the input contains two integers n and k (1 ≤ n ≤ 100 000, 0 ≤ k ≤ n) — the length of the string and the maximum number of characters to change.

The second line contains the string, consisting of letters ‘a’ and ‘b’ only.

Output

Print the only integer — the maximum beauty of the string Vasya can achieve by changing no more than k characters.

题意很好理解，做法只是很暴力地扫描两遍，第一次只考虑把字母改变成a，第二次是b， 取最大值。在每一次扫描的时候，保持左端点不变，尽可能增加右端点，取出最大值，然后 递增左端点，然后再尽可能地增加右端点。如果右端点到达字符串的最右端，这一趟就结束 了。

程序嘛，反正过了，也没再修改……:joy: :joy: 回头有时间再改改吧。。。

char str[100000+10];
int n, k;
int solve (char ch) {
    int i, j, max_len = 0, k1 = k, tmp_len = 0;
    i = j = 0;

    while (1) {
      while (1) {
        if (j >= n) break;

        if (str[j] != ch) {
          if (k1 > 0) k1--;
          else break;
        } 

        tmp_len++;

        if (tmp_len > max_len) {
          max_len = tmp_len;
        }

        ++j;
      }

      if (str[i] != ch) {
        k1++;
      }

      ++i;
      tmp_len--;

      if (j >= n) break;
    }

    return max_len;
}
  int
main ( int argc, char *argv[] )
{
#ifndef  ONLINE_JUDGE
freopen("b.in", "r", stdin);
#endif     /* -----  ONLINE_JUDGE  ----- */
  

  while ( ~scanf("%d%d", &n, &k) ) {
    scanf("%s", str);
    int res1 = solve('a');
    int res2 = solve('b');
    if (res1 > res2) {
      printf ( "%d\n", res1 );
    } else {
      printf ( "%d\n", res2 );
    }
  }

    return EXIT_SUCCESS;
}				/* ----------  end of function main  ---------- */

今天跑步5.19km

跑跑步也挺好的

今天跑步换了一双鞋，跑到半路发现我的鞋磨脚，真是醉了……:smile: 最终还是跑完了，回 来一看脚掌侧面磨了一个泡。。。:joy: 蛮拼的……