各 \(0 \leq i \leq N\) に対して，\(s\) の先頭 \(i\) 文字に含まれる 0 の個数 \(-\) 1 の個数を \(v_i\) とおくことにします． \(s\) の辞書順最小化は，\(v\) の辞書順最大化に対応しています． \(v\) の満たすべき条件は，以下のようなものです．

• \(|v_i-v_{i+1}|=1\)
• \(v_{L_i-1}=v_{R_i}\)

ここで，最初の条件を \(|v_i-v_{i+1}| \leq 1\) とすれば，\(v\) の辞書順最大化，より正確には \(v\) の各項の最大化は簡単です． これは，不等式制約を最短路問題に帰着して解けばよいです． （いわゆる牛ゲーと呼ばれるテクニックです）

ところで，こうして得た解は，実は \(|v_i-v_{i+1}|=1\) を満たしています． これは各 \(v_i\) の偶奇が定まることから確認できます．

今回解くべき最短路問題は辺の重みが \(0\) と \(1\) だけなので，\(O(N+M)\) で解くことが可能です． dijkstra 法を使って \(O((N+M)\log(N+M))\) でもかまいません．