Ex - Sequence of Substrings Editorial /

Time Limit: 5 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

0 と 1 のみからなる長さ N の文字列 S = s_1 s_2 \ldots s_N が与えられます。

整数の 2 つ組を K 個並べた列 \big((L_1, R_1), (L_2, R_2), \ldots, (L_K, R_K)\big) であって以下の 3 つの条件をすべて満たすものが存在するような最大の整数 K を出力してください。

  • i = 1, 2, \ldots, K について、1 \leq L_i \leq R_i \leq N
  • i = 1, 2, \ldots, K-1 について、R_i \lt L_{i+1}
  • i = 1, 2, \ldots, K-1 について、文字列 s_{L_i}s_{L_i+1} \ldots s_{R_i} は文字列 s_{L_{i+1}}s_{L_{i+1}+1}\ldots s_{R_{i+1}} より辞書順で真に小さい

制約

  • 1 \leq N \leq 2.5 \times 10^4
  • N は整数
  • S は 0 と 1 のみからなる長さ N の文字列

入力

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

N
S

出力

答えを出力せよ。

入力例 1

7
0101010

出力例 1

3

K = 3 のとき、例えば (L_1, R_1) = (1, 1), (L_2, R_2) = (3, 5), (L_3, R_3) = (6, 7) が問題文中の条件を満たします。 実際、s_1 = 0 は s_3s_4s_5 = 010 より辞書順で真に小さく、s_3s_4s_5 = 010 は s_6s_7 = 10 より辞書順で真に小さいです。
K \geq 4 のときは、問題文中の条件を満たす \big((L_1, R_1), (L_2, R_2), \ldots, (L_K, R_K)\big) は存在しません。

入力例 2

30
000011001110101001011110001001

出力例 2

9

Score : 600 points

Problem Statement

You are given a string S = s_1 s_2 \ldots s_N of length N consisting of 0's and 1's.

Find the maximum integer K such that there is a sequence of K pairs of integers \big((L_1, R_1), (L_2, R_2), \ldots, (L_K, R_K)\big) that satisfy all three conditions below.

  • 1 \leq L_i \leq R_i \leq N for each i = 1, 2, \ldots, K.
  • R_i \lt L_{i+1} for i = 1, 2, \ldots, K-1.
  • The string s_{L_i}s_{L_i+1} \ldots s_{R_i} is strictly lexicographically smaller than the string s_{L_{i+1}}s_{L_{i+1}+1}\ldots s_{R_{i+1}}.

Constraints

  • 1 \leq N \leq 2.5 \times 10^4
  • N is an integer.
  • S is a string of length N consisting of 0's and 1's.

Input

Input is given from Standard Input in the following format:

N
S

Output

Print the answer.

Sample Input 1

7
0101010

Sample Output 1

3

For K = 3, one sequence satisfying the conditition is (L_1, R_1) = (1, 1), (L_2, R_2) = (3, 5), (L_3, R_3) = (6, 7). Indeed, s_1 = 0 is strictly lexicographically smaller than s_3s_4s_5 = 010, and s_3s_4s_5 = 010 is strictly lexicographically smaller than s_6s_7 = 10.
For K \geq 4, there is no sequence \big((L_1, R_1), (L_2, R_2), \ldots, (L_K, R_K)\big) satisfying the condition.

Sample Input 2

30
000011001110101001011110001001

Sample Output 2

9