Rearranging Hikes on a Route

Hard

A mountain route is written as a string route of 1s (a step up) and 0s (a step down). The route is *balanced*: it never drops below its starting height and ends back at that height. In other words, every prefix has at least as many ones as zeros, and the whole string has equally many of each. Call a non-empty substring that is balanced on its own a *hike*. In one move you may take two hikes that sit right next to each other and swap them. You may make any number of moves. Return the lexicographically largest string you can obtain.

Example 1

route='10110010' → '11001010'

The route splits into three adjacent hikes: 10, 1100 and 10. Swapping the first two gives 11001010, and nothing improves it further.

Example 2

route='111000101100' → '111000110010'

The route consists of the hikes 111000, 10 and 1100. The first already opens with the steepest climb, and the last two are worth swapping: 111000110010.

Example 3

route='10' → '10'

Constraints

1 ≤ len(route) ≤ 50
route consists of the characters 0 and 1
route is balanced

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Recursion String

Similar problems

Pattern With Dot and Star Hard Does the Text Fit the Pattern Hard Plus-Minus Calculator With Brackets Hard Flip-Proof Numbers in a Range Hard Amount in Words Hard

Input

route='10110010'

Expected

'11001010'

Run checks the first 3 tests in your browser. Submit checks all 95 tests on the server, hidden ones included.