Ryan was tidying up his house for the party when he stumbled upon a messy string hidden under the carpets. Eager to clean it up in a precise and stylish manner, he decided to make it as clean as possible using a specific set of moves.Problem Constraints
The string, denoted as s, is a binary string of length n, consisting solely of 0s and 1s. Ryan can perform a move by selecting two consecutive characters si and si+1. If si is 1 and si+1 is 0, he can erase exactly one of them. The string shrinks after each erasure.
Ryan can make an arbitrary number of moves (possibly zero) and aims to create the cleanest possible string. He defines cleanliness such that for two different strings x and y, the shorter string is considered cleaner. If the lengths are the same, the lexicographically smaller string is cleaner.
Your task is to print the cleanest possible string that Ryan can obtain by performing some number of moves.
1 =< n <= 105 Input Format
The first argument is the string.Output Format
Return the cleanest string Ryan can achieve after performing some number of moves (possibly zero).Example Input
For Input 1:
Ryan can't perform any moves.
For Input 2:
Ryan should erase s2.
NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified.
Still have a question? Checkout Sample Codes for more details.