\(R\neq|S|\) のとき最善ではありません。\(R=|S|\) として良いです。最適な \(L\) を求めることを考えます。\(S\) の \(i\) 文字目以降の部分を取り出してできる文字列を \(T_i\) と書くことにします。

各 \(i\) について、\((L,R)=(i,|S|)\) のときの最適な \(p\) を計算しておきます。これは \(O(\sigma|S|)\) 時間で計算できます。さらに、\(S_i\) をその \(p\) で変換した文字列を \(T'_i\) と書くことにします。

\(T_L\) を順列で変換したときに辞書順最大となる \(L\) を計算したいのでした。\(i,j\) に対し、\(T'_i\) と \(T'_j\) の大小関係を高速に計算できれば良いです。これの代わりに、\(T'_i\) と \(T'_j\) の LCP の長さを計算できれば良いです。以降これを高速に計算することを目標にします。

文字 \(c\) について長さ \(|S|\) の文字列 \(A_c\) を次のように定めます。

• \(A_c\) の \(i\) 文字目は、\(S\) の \(i\) 文字目が \(c\) ならば 1、そうでないならば 0。

\(A_c\) を \(c\) の昇順に結合したものを \(B\) とします。

\(T'_i\) と \(T'_j\) の LCP は B 上の区間同士の LCP を \(\sigma\) 回計算することで計算できます。

以上で、この問題を \(O(\sigma|S|\log(\sigma|S|))\) 時間で解くことができます。