Given a sequence of intervals [Li, Ri], try to transform them one by one using L+, L-, R+, R- in the shortest operation sequence. Tie breaker is the lexicographical order.
Actually, you only need to consider how to transform [A, B] to [C, D].
The first key point is that, the length of shortest operation sequence equals to |A - C| + |B - D|. This is almost straightforward, because we can always move one end towards its target.
The second one is that we can enumerate the next step (4 operations) and greedily choose the minimum one (both length and lexicographical order). This is because the lexicographical order is determined by the first different character.
The only trick is to remember that you must avoid L = R during this process.
This algorithm’s time complexity is O(Len), where Len is the length of output.