Special Binary String

The rules are simple to state but hard to picture, so the most direct plan is to try everything. Start from s, apply every possible move, then apply every possible move to each new string, and keep going until no new string appears. The largest string seen along the way is the answer.

Two pieces of work make this possible.

Listing every move of a string t. A move is fixed by three positions i < j < k where t[i:j] and t[j:k] are both special. To find every special substring that starts at i, walk right from i keeping a balance: +1 for each 1 and −1 for each 0.

• Each time the balance comes back to 0, the stretch so far is special.
• The moment the balance goes below 0, stop. No longer stretch starting at i can be special, because its prefix already has more 0s than 1s.

Do this for every i to get every valid end j. Then, for each such j, every valid end k of a special substring starting at j gives one move.

Not doing the same work twice. Many moves lead back to strings we have already met. Swapping two identical pieces, for example, gives the same string back. So keep a set of seen strings and a queue of strings still to expand. Take a string off the queue, try all its moves, and add only the results that are new. This is a breadth-first search over strings.

We trace Example 1, s = "10110010". In each move the first piece is highlighted in amber and the second in indigo; the row underneath is the string after the swap.

Step 1: Put "10110010" in the queue and in the seen set. The best string so far is "10110010" itself.

Step 2: Expand "10110010": swap "10" (positions 0–1) with "1100" (positions 2–5) → "11001010". New — add it to the queue. The best is now "11001010".

Step 3: Swap "10" (positions 0–1) with "110010" (positions 2–7) → "11001010". Already seen — skip.

Step 4: Swap "101100" (positions 0–5) with "10" (positions 6–7) → "10101100". New — add it to the queue.

Step 5: Swap "1100" (positions 2–5) with "10" (positions 6–7) → "10101100". Already seen — skip.

Step 6: Expand "11001010": swap "1100" (positions 0–3) with "10" (positions 4–5) → "10110010". Already seen — skip.

Step 7: Swap "1100" (positions 0–3) with "1010" (positions 4–7) → "10101100". Already seen — skip.

Step 8: Swap "110010" (positions 0–5) with "10" (positions 6–7) → "10110010". Already seen — skip.

Step 9: Swap "10" (positions 4–5) with "10" (positions 6–7) → "11001010", the same string, because the pieces are equal. Nothing new.

Step 10: Expand "10101100": swap "10" (positions 0–1) with "10" (positions 2–3) → "10101100", the same string, because the pieces are equal. Nothing new.

Step 11: Swap "10" (positions 0–1) with "101100" (positions 2–7) → "10110010". Already seen — skip.

Step 12: Swap "1010" (positions 0–3) with "1100" (positions 4–7) → "11001010". Already seen — skip.

Step 13: Swap "10" (positions 2–3) with "1100" (positions 4–7) → "10110010". Already seen — skip.

Step 14: The queue is empty. Of the 3 strings reachable from "10110010", the largest is "11001010".

1. Put s in a queue and in a set seen. Let best = s.
2. While the queue is not empty:
   • Take the next string t off the queue and set best = max(best, t).
   • For every i, list each j such that t[i:j] is special (balance back to 0, never below 0).
   • For every i, every such j, and every k such that t[j:k] is special:
     • Build u = t[:i] + t[j:k] + t[i:j] + t[k:].
     • If u is not in seen, add it to seen and to the queue.
3. Return best.

Let n be the length of s and R the number of different strings reachable from it.

Time Complexity: O(R · n⁴). For each reachable string, listing the special ends takes O(n²). A string can have up to O(n³) moves, and building each resulting string takes O(n).

Space Complexity: O(R · n). Every reachable string is kept in the seen set.

Everything depends on R, and R can be enormous. That is the problem, as the next section shows.

Look at the walk again. Each time it comes back down to the ground, one mountain ends. A special string is a row of mountains standing side by side. Every mountain has the same shape: a first step up (1), then some walk that never goes below that first step, then a final step down (0). The part in between, the mountain's inside, starts and ends at the same height and never dips below it, so the inside is a special string of its own.

Three facts about moves follow from this picture.

1. A move never breaks a mountain. A special substring starts and ends at the same height and never dips below it, so it is always one or more whole mountains standing on the same floor. A move therefore swaps two neighbouring groups of whole mountains on one floor. It can change their order, but it cannot split a mountain or move part of one somewhere else. What happens inside a mountain stays inside it.
2. Any order of the mountains on a floor can be reached. Two neighbouring mountains are two neighbouring special substrings, so swapping them is always a legal move. By swapping neighbours again and again, the way you would sort a hand of cards, you can put the mountains on a floor in any order you like.
3. Every inside is its own smaller puzzle. The inside of a mountain is a special string, and moves inside it follow exactly the same rules, independently of everything else.

So the problem splits cleanly. Cut s into its mountains. Rebuild each mountain as "1" + best(inside) + "0", solving its inside with the very same function. Making a piece larger never hurts: with everything else fixed, a larger piece in the same place makes the whole string larger. Then choose the order of the pieces.

For that last choice, this approach simply tries every order. Pick which piece goes first, then find the best order of the rest the same way, and keep the largest result. When several pieces are identical, trying each of them first gives the same strings, so each different piece is tried only once in each position.

We trace Example 1 again, s = "10110010". The row shows the pieces; while orders are being tried, the row underneath shows the string that order produces.

Step 1: Split "10110010" where the balance returns to 0 (after positions 1, 5 and 7): the mountains are "10", "1100" and "10".

Step 2: Mountain 0, "10": its inside is empty — nothing to rearrange.

Step 3: Mountain 1, "1100": its inside "10" is special and already at its best, so the piece stays "1100".

Step 4: Mountain 2, "10": its inside is empty — nothing to rearrange.

Step 5: Order 1, "10" + "10" + "1100" = "10101100" — the best so far.

Step 6: Order 2, "10" + "1100" + "10" = "10110010" — larger than "10101100", the new best.

Step 7: Order 3, "1100" + "10" + "10" = "11001010" — larger than "10110010", the new best.

Step 8: Every distinct order has been tried. Three pieces can be lined up in 3! = 6 ways, but the two "10" pieces are identical, so only 3 strings are different. Return "11001010".

best(s):

1. Walk through s with a balance (+1 for 1, −1 for 0). Each time the balance returns to 0, one mountain s[start..i] has ended:
   • Its inside is s[start+1..i-1]. Rebuild the piece as "1" + best(inside) + "0".
   • Start the next mountain at i + 1.
2. Count how many copies of each different piece there are.
3. best_order(pieces left): if none are left, return "". Otherwise, for each different piece that still has a copy left, take one copy, form piece + best_order(rest), put the copy back, and keep the largest result.
4. Return best_order(all pieces).

Let n be the length of s.

Time Complexity: the recursion into insides is cheap. Each floor is handled once, and each call scans its own part of the string. The cost is in trying orders. If a floor holds m pieces, and identical pieces appear c₁, c₂, … times, the number of different orders is m! / (c₁! × c₂! × …), where m! means 1 × 2 × … × m. Building each candidate costs up to O(n). That count grows factorially, faster than any power of m, as pieces are added to a floor.

Space Complexity: O(n²). The chain of unfinished calls is at most about n/2 deep, and each holds strings of length up to n.

Within this problem's limits it survives. The most orders a single floor of a 50-character string can have is 720,720, and on that input this approach took about 0.6 s in Python and 0.04 s in C++.

Suppose two pieces stand next to each other, A first and then B, and B is larger than A. Swapping them is a legal move. Is the result larger?

Compare A + B with B + A. Neither mountain can be the beginning of the other. A mountain only touches the floor at its very last step, so if A were the start of B, the walk of B would touch the floor where A ends, before B's own end — impossible. So A and B differ somewhere inside both of them, and B has the 1 at the first place they differ. B + A and A + B differ first at that very same place, so B + A is larger. Everything before and after the pair is unchanged, so the whole string gets larger.

That settles it. In the best order, no piece can be followed by a larger one, or swapping the two would improve it. So the pieces must stand largest first, and that is exactly what sorting in descending order produces. This is also why the trap from the previous section cannot happen here. There, "1" was the beginning of "10", and mountains are never the beginning of one another.

The whole solution is the recursion from before, with sorting in place of trying orders:

best(s) = cut s into mountains, rebuild each as "1" + best(inside) + "0", sort the pieces from largest to smallest, and join them.

We trace Example 2, s = "101101101000". Each box is one call of best. A box is amber while it runs, indigo while it waits for one of its insides to be solved, and green, with its answer underneath, once it returns.

Step 1: best("101101101000") cuts the string where the balance returns to 0: "10" | "1101101000".

Step 2: Mountain "10" has an empty inside: best("") returns "" at once.

Step 3: Mountain "1101101000" has the inside "10110100". best("10110100") cuts it into "10" | "110100".

Step 4: Mountain "10" has an empty inside: best("") returns "" at once.

Step 5: Mountain "110100" has the inside "1010". best("1010") cuts it into "10" | "10".

Step 6: Mountain "10" has an empty inside: best("") returns "" at once.

Step 7: Mountain "10" has an empty inside: best("") returns "" at once.

Step 8: Back in best("1010"): the rebuilt pieces are "10", "10". Sorted largest first they give "1010".

Step 9: Back in best("10110100"): the rebuilt pieces are "10", "110100". Sorted largest first they give "11010010".

Step 10: Back in best("101101101000"): the rebuilt pieces are "10", "1110100100". Sorted largest first they give "111010010010".

best(s):

1. Set balance = 0, start = 0, and an empty list pieces.
2. For each position i in s:
   • Add 1 to balance for a 1, subtract 1 for a 0.
   • If balance is 0, then s[start..i] is one mountain:
     • Append "1" + best(s[start+1..i-1]) + "0" to pieces.
     • Set start = i + 1.
3. Sort pieces from largest to smallest.
4. Return the pieces joined together. For an empty s this is "".

Let n be the length of s.

Time Complexity: O(n²).

• Scanning. Every call scans its own string once. A character is scanned once by each call whose string contains it, and there are at most n/2 such calls, one per level of nesting. So all the scanning together is at most n × n/2.
• Sorting. Sorting the pieces of one call compares strings whose lengths add up to that call's length. Over the whole recursion this adds no more than the same O(n²).

Space Complexity: O(n²) in the worst case. For a deeply nested string like "111…000", about n/2 calls are unfinished at once, and each holds its own copy of a string up to n long.

At full size the cost is negligible. On the 50-character input above with 720,720 orders on one floor, this version took about 0.02 s in Python, and the C++ run finished in under 0.01 s.