Flip and Reverse
Contest: Codeforces Round 691 (Div. 1)
Difficulty rating: 3100
Tags: data structures, graphs, greedy

You are given a string $$$s$$$ of 0's and 1's. You are allowed to perform the following operation:

- choose a non-empty contiguous substring of $$$s$$$ that contains an equal number of 0's and 1's;
- flip all characters in the substring, that is, replace all 0's with 1's, and vice versa;
- reverse the substring.

For example, consider $$$s$$$ = 00111011, and the following operation:

- Choose the first six characters as the substring to act upon: 00111011. Note that the number of 0's and 1's are equal, so this is a legal choice. Choosing substrings 0, 110, or the entire string would not be possible.
- Flip all characters in the substring: 11000111.
- Reverse the substring: 10001111.

Find the lexicographically smallest string that can be obtained from $$$s$$$ after zero or more operations.

Input format:
The first line contains a single integer $$$T$$$ ($$$1 \leq T \leq 5 \cdot 10^5$$$) — the number of test cases. Each of the following $$$T$$$ lines contains a single non-empty string — the input string $$$s$$$ for the respective test case.

All strings consist of characters 0 and 1, and their total length does not exceed $$$5 \cdot 10^5$$$.

Output format:
For each test case, on a separate line print the lexicographically smallest string that can be obtained from $$$s$$$ after zero or more operations.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the first test case a single operation should be applied to the entire string.

In the second test case two operations are needed: 0111001, 0110110.

In the third test case the string stays the same after any operation.

Example input:
3
100101
1100011
10101010

Example output:
010110
0110110
10101010

Editorial:
Let's go over characters of $$$s$$$ left to right and keep track of the balance = (the number of $$$0$$$'s) - (the number of $$$1$$$'s) among the visited characters. We can think about starting at the point $$$0$$$, and moving right (from $$$x$$$ to $$$x + 1$$$) when we see a $$$0$$$, and moving left (to $$$x - 1$$$) when we see a $$$1$$$. Each time we go from $$$x$$$ to $$$x \pm 1$$$, let's connect the two points with an edge. We'll keep track of all the edges, even if there are multiple ones connecting the same pair of points. Since our path visits all edges we've created exactly once, it is an Eulerian path in the (multi)graph constructed this way. The start point of the path is $$$0$$$, and the finish point is equal to the total balance of the string $$$s$$$.
Now, let's think about what a transformation does. A valid substring subject to the transformation has an equal number of $$$0$$$'s and $$$1$$$'s, thus it must correspond to a part of our path which is a round tour from a point $$$x$$$ back to itself. Flipping and reversing the substring makes us traverse all the same edges, but in reverse order and in reverse direction. Thus, in terms of graphs and paths, what we're doing is reversing a cycle that occurs in the Eulerian path. Note that the collection of edges is preserved after every operation, in other words, the graph is an invariant of the process. Furthermore, the start and finish of the path also stay the same.
The answer (= lex. min. string) thus also corresponds to a certain Eulerian path in the very same graph, but which one? It should be the lex. min. path (where we prefer going right before going left) that is obtainable from the initial one with cycle reverses. However, the important observation is: in this particular graph any Eulerian path is obtainable from any other one with cycle reverses (as long as they start and finish in the same places).
There are a few ways to prove this. For example, consider two Eulerian paths, and look at the first point where they diverge: say, one goes $$$x \to x + 1$$$, while the other goes $$$x \to x - 1$$$. But both paths will have to eventually return to $$$x$$$ to go in the other direction, thus there is at least one extra edge in each direction $$$x \to x + 1$$$ and $$$x \to x - 1$$$, unvisited before the divergence happened. Let's wait until the first path visits at least two edges between $$$x$$$ and $$$x - 1$$$, returning back to $$$x$$$, and reverse the resulting cycle. With this, the next edge after diverging have changed from $$$x \to x + 1$$$ to $$$x \to x - 1$$$, and now the two paths diverge some time later. We can proceed until both paths are the same.
The observation implies that we should simply look for the lex. min. Eulerian path in the entire graph. Let's try to do this greedily: build the path from the beginning, marking edges as used when we traverse them. Take the transition $$$x \to x + 1$$$ whenever there is a unused edge leading there, otherwise settle for $$$x \to x - 1$$$. There is a caveat, though: we can not go $$$x \to x + 1$$$ if this uses the last edge between $$$x$$$ and $$$x + 1$$$, and additionally we still have to visit $$$x$$$ some time later (say, if $$$x$$$ has unused edges to $$$x - 1$$$). However, with this extra condition in place, the greedy algorithm will always find an Eulerian path, and it's clearly the lex. min. one. This procedure is fairly easy to implement in linear time: reconstruct the graph and do the greedy thing.