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.
这题的核心是理解“good binary string”的递归结构：一个合法串可以分解成若干个相邻的 good 子串，而每个 good 子串都满足 0 和 1 数量相等，且任意前缀中 1 的数量不少于 0。为了让结果字典序 / 数值最大，做法是先递归处理每个最外层的 good 子串内部，再把这些子串按整体大小降序排列后重新拼接。样例 1010111000 会被拆成 1010 和 111000 两段，交换后得到 1110001010，这是可以达到的最大值。由于字符串长度很小，直接用递归分割 + 排序即可，通常结合栈或计数扫描来找最外层边界。
