/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
この問題における 11/22 文字列の定義は A 問題および E 問題と同じです。
文字列 T が以下の条件を全て満たすとき、T を 11/22 文字列 と呼びます。
- |T| は奇数である。ここで、|T| は T の長さを表す。
- 1 文字目から \frac{|T|+1}{2} - 1 文字目までが
1である。 - \frac{|T|+1}{2} 文字目が
/である。 - \frac{|T|+1}{2} + 1 文字目から |T| 文字目までが
2である。
例えば 11/22, 111/222, / は 11/22 文字列ですが、1122, 1/22, 11/2222, 22/11, //2/2/211 はそうではありません。
1, 2, / からなる長さ N の文字列 S が与えられます。S は / を 1 個以上含みます。
11/22 文字列であるような S の(連続な)部分文字列の長さの最大値を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- S は
1,2,/からなる長さ N の文字列 - S は
/を 1 個以上含む
入力
入力は以下の形式で標準入力から与えられる。
N S
出力
11/22 文字列であるような S の(連続な)部分文字列の長さの最大値を出力せよ。
入力例 1
8 211/2212
出力例 1
5
S の 2 文字目から 6 文字目からなる部分文字列は 11/22 で、これは 11/22 文字列です。S の部分文字列のうち 11/22 文字列であるものはこれが最長です。よって 5 が答えです。
入力例 2
5 22/11
出力例 2
1
入力例 3
22 /1211/2///2111/2222/11
出力例 3
7
Score : 300 points
Problem Statement
The definition of an 11/22 string in this problem is the same as in Problems A and E.
A string T is called an 11/22 string when it satisfies all of the following conditions:
- |T| is odd. Here, |T| denotes the length of T.
- The 1-st through (\frac{|T|+1}{2} - 1)-th characters are all
1. - The (\frac{|T|+1}{2})-th character is
/. - The (\frac{|T|+1}{2} + 1)-th through |T|-th characters are all
2.
For example, 11/22, 111/222, and / are 11/22 strings, but 1122, 1/22, 11/2222, 22/11, and //2/2/211 are not.
You are given a string S of length N consisting of 1, 2, and /, where S contains at least one /.
Find the maximum length of a (contiguous) substring of S that is an 11/22 string.
Constraints
- 1 \leq N \leq 2 \times 10^5
- S is a string of length N consisting of
1,2, and/. - S contains at least one
/.
Input
The input is given from Standard Input in the following format:
N S
Output
Print the maximum length of a (contiguous) substring of S that is an 11/22 string.
Sample Input 1
8 211/2212
Sample Output 1
5
The substring from the 2-nd to 6-th character of S is 11/22, which is an 11/22 string. Among all substrings of S that are 11/22 strings, this is the longest. Therefore, the answer is 5.
Sample Input 2
5 22/11
Sample Output 2
1
Sample Input 3
22 /1211/2///2111/2222/11
Sample Output 3
7