For each \(0 \leq i \leq N\), let \(v_i\) be the number of 0s in the first \(i\) characters of \(s\) minus the number of 1s in those characters. Minimizing \(s\) lexicographically corresponds to maximizing \(v\) lexicographically. The conditions that \(v\) should satisfy are:

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

Here, suppose we replace the first condition with \(|v_i-v_{i+1}| \leq 1\). In that case, it is easy to maximize \(v\) lexicographically, or, more accurately, maximizing the terms of \(v\), by rephrasing inequality constraints into a shortest path problem. (Some call this “cow technique”.)

Actually, it turns out that the solution to this satisfies \(|v_i-v_{i+1}|=1\), which can be verified from the fact that the parity of each \(v_i\) is fixed.

Since the shortest path problem this time has only edges of weight \(0\) or \(1\), it can be solved in \(O(N+M)\), or \(O((N+M)\log(N+M))\) with Dijkstra’s algorithm.