\(S\) の \(l\) 文字目から \(r\) 文字目までからなる部分文字列 \(s_l s_{l+1} \ldots s_r\) を \(S[l, r]\) で表します。

本問題は直感的には次のように解釈できます

\(S\) からいくつかの連続な部分文字列（以下、単に「部分文字列」）を切り取る。部分文字列を切り取る区間どうしは重なってはならない。さらに、切り取った部分文字列を \(S\) の先頭に近いものから順に並べた列

\[ S[L_1, R_1], S[L_2, R_2], \ldots, S[L_K, R_K] \]

は辞書順で狭義単調増加でならなければならない。最大でいくつの部分文字列を \(S\) から切り取れるか？

動的計画法によって最長増加部分列（LIS）を求めるのと似た、以下のアルゴリズムによってこの問題を解くことができます。

1. まず、\(1 \leq l \leq r \leq N\) を満たすすべての整数の組 \((l, r)\) を、\(S[l, r]\) の辞書順で昇順にソート（ \(S[l, r]\) が等しい \((l, r)\) どうしはさらに \(l\) の降順にソート）した列を \((l_1, r_1), (l_2, r_2), \ldots, (l_M, r_M)\)とする。
2. 一次元配列 \(\mathrm{dp}[\ast]\) を準備し、\(\mathrm{dp}[0] \leftarrow 0\) および、\(i = 1, 2, \ldots, N\) について \(\mathrm{dp}[i] \leftarrow -\infty\) と初期化する。
3. \(i = 1, 2, \ldots, M\) の順に次を行う 。
   • \(\mathrm{dp}[r_i] \leftarrow \max\lbrace \mathrm{dp}[r_i], \max\lbrace \mathrm{dp}[0], \mathrm{dp}[1], \mathrm{dp}[2], \ldots, \mathrm{dp}[l_i-1] \rbrace + 1 \rbrace\)
4. 本問題の答えは \(\max \lbrace \mathrm{dp}[1], \mathrm{dp}[2], \ldots, \mathrm{dp}[N] \rbrace\) として得られる。

手順1. を行う際には、例えば、 \(S\) のすべての接尾辞 \(S[1, N], S[2, N] , \ldots, S[N, N]\) を持つTrie木を構築し、その各ノードを深さ優先探索における行きがけ順で番号付することで、\(S\) の部分文字列としてあり得るすべての文字列に対して、辞書順の大小関係を保つ番号付を行うことができます。これを用いて手順 1. を \(\mathrm{O}(N^2)\) 時間（あるいは \(\mathrm{O}(N^2\log N)\) 時間）で実現できます。
また、配列 \(\mathrm{dp}[\ast]\) をセグメント木を用いて管理することで、手順 2. から 4. は\(\mathrm{O}(N^2\log N)\) 時間で実現することができます。

以上より、上記のアルゴリズムを全体で \(\mathrm{O}(N^2\log N)\) 時間で動作するように実装することができます。 しかし、このままでは実行制限時間に間に合わせることは困難なので、この方法を高速化することを考えます。

ここで、\(1+2+3+\cdots+b \leq N\) を満たす最大の整数 \(b\) を \(B\) とおきます。実は「切り取る文字列の長さは高々 \(B\) である」という制約を課しても、本問題の答えは変わりません。 なぜなら、最適解 \(\big((L_1, R_1), (L_2, R_2), \ldots, (L_K, R_K)\big)\) が任意に与えられたとき、この最適解に対して以下を行うことで、すべての \(i = 1, 2, \ldots, K\) で \(R_i-L_i+1 \leq B\) を満たす最適解が得られるからです。

• \(R_i-L_i+1 \gt B\) となる \(1 \leq i \leq K\) が存在する限り、次を繰り返す。
  • \(R_i-L_i+1 \gt B\) となる \(1 \leq i \leq K\) に対して、\(j = 1, 2, \ldots, i-1\)のうち少なくとも \(1\) つが \((R_j-L_j+1)+1 \lt R_{j+1}-L_{j+1}+1\) を満たす。
  • そのような \(j\) を\(1\) つ選び、\((L_{j+1}, R_{j+1})\) を \((L_{j+1}, R_{j+1}-1)\) に置き換える。

したがって、先述の \(\mathrm{O}(N^2\log N)\) 時間のアルゴリズムを、

\(1 \leq l \leq r \leq N\) を満たす整数の組 \((l, r)\) すべてを扱うのではなく、\(r-l+1 \leq B\) を満たす組 \((l, r)\) のみを扱う

ように修正しても本問題の正しい答えが得られます。 この改良によって、本問題を \(\mathrm{O}(NB\log N) = \mathrm{O}(N\sqrt{N}\log N)\) 時間で解くことができます。