Lexicographically Largest Special Binary String

Problem Preview

"A binary string is called special if: The number of 1s is equal to the number of 0s. For every prefix of the string, the number of 1s is greater than or equal to the number of 0s. You are given a special binary string S. In one operation, you may choose two adjacent special substrings and swap them. Your task is to obtain the lexicographically largest string possible after performing any number of operations. ### Problem ### Input A single line containing a binary string S. ### Output Print the lexicographically largest string obtainable. ### Constraints - 1 ≤ |S| ≤ 5 × 10^4 - S is guaranteed to be a special binary string. ### Example 1 #### Input 11011000 #### Output 11100100 #### Explanation The string can be decomposed into special substrings and rearranged optimally: 11011000 → 1100 + 1000 → rearrange recursively → 11100100"