Given a good binary string, binString, perform zero or more swap operations on its adjacent good substrings such that the resulting string is the largest possible numeric value.
Two substrings are adjacent if the last character of the first substring occurs exactly one index before the first character of the second substring.
Example
binString = 1010111000
There are two good binary substrings, 1010 and 111000, among others. Swap these two substrings to get a larger value: 1110001010. This is the largest possible good string that can be formed.
Complete the function largestMagical below.
- The function is expected to return a
STRING. - The function accepts
STRING binStringas parameter.
Returns
The largest possible binary value as a string.
Constraints
- Each character of
binStringis{0,1}. 1 <= |binString| <= 50binStringis a good string.
The key idea is to use the recursive structure of a good binary string: split the string into its top-level good substrings, recursively maximize each part, and then sort those parts in descending order before concatenation. A good substring has the same number of 0s and 1s, and every prefix has at least as many 1s as 0s. For the example 1010111000, the top-level pieces are 1010 and 111000, and swapping them yields 1110001010, which is the maximum possible result. With the small length limit, a recursive scan and sort is the cleanest solution.
