296. Special Binary String

A special binary string is a binary string where the number of 0s equals the number of 1s and every prefix has at least as many 1s as 0s. You may repeatedly swap two adjacent special substrings. Given such a string s, return the lexicographically largest string obtainable.

Input: A quoted special binary string.

Output: Quoted string — the largest reachable string.

Examples

Input: "11011000"
Output: "11100100"
Explanation: Swap special substrings to maximize.

Input: "10"
Output: "10"
Explanation: Single unit.

Input: "1100"
Output: "1100"
Explanation: Already maximal.

Constraints

• 1<=s.length<=50
• s is a special binary string

Asked by