D - Wide Flip Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 500 点

問題文

0 と 1 からなる文字列 S が与えられます。 以下の操作を好きな回数繰り返すことで S の要素をすべて 0 にできるような、|S| 以下の最大の整数 K を求めてください。

  • S の長さ K 以上の連続する区間 [l,r] を選ぶ(すなわち、r-l+1\geq K が満たされる必要がある)。l\leq i\leq r なるすべての整数 i に対し、S_i が 0 なら S_i を 1 に、S_i が 1 なら S_i を 0 に置き換える。

制約

  • 1\leq |S|\leq 10^5
  • S_i(1\leq i\leq N) は 0 または 1 である

入力

入力は以下の形式で標準入力から与えられる。

S

出力

操作を好きな回数繰り返すことで S の要素をすべて 0 にできるような 最大の (21:08 JST 修正) 整数 K を出力せよ。

入力例 1

010

出力例 1

2

以下の操作で、S の要素をすべて 0 にできます。

  • 長さ 3 の区間 [1,3] に操作を行う。S は 101 になる。
  • 長さ 2 の区間 [1,2] に操作を行う。S は 011 になる。
  • 長さ 2 の区間 [2,3] に操作を行う。S は 000 になる。

入力例 2

100000000

出力例 2

8

入力例 3

00001111

出力例 3

4

Score : 500 points

Problem Statement

You are given a string S consisting of 0 and 1. Find the maximum integer K not greater than |S| such that we can turn all the characters of S into 0 by repeating the following operation some number of times.

  • Choose a contiguous segment [l,r] in S whose length is at least K (that is, r-l+1\geq K must be satisfied). For each integer i such that l\leq i\leq r, do the following: if S_i is 0, replace it with 1; if S_i is 1, replace it with 0.

Constraints

  • 1\leq |S|\leq 10^5
  • S_i(1\leq i\leq N) is either 0 or 1.

Input

Input is given from Standard Input in the following format:

S

Output

Print the maximum integer K such that we can turn all the characters of S into 0 by repeating the operation some number of times.

Sample Input 1

010

Sample Output 1

2

We can turn all the characters of S into 0 by the following operations:

  • Perform the operation on the segment S[1,3] with length 3. S is now 101.
  • Perform the operation on the segment S[1,2] with length 2. S is now 011.
  • Perform the operation on the segment S[2,3] with length 2. S is now 000.

Sample Input 2

100000000

Sample Output 2

8

Sample Input 3

00001111

Sample Output 3

4