Final Recursive Form | Commented and Explained
Intuition\n Describe your first thoughts on how to solve this problem. \nIn the intuition, I\'m stepping through the start of the problem and the outline of the
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nIn the intuition, I\'m stepping through the start of the problem and the outline of the example as a recursive backtrack. Backtracking is not used here, but serves to inform the thinking process and outline some things worth finding in pursuing the solution. \n\nFirst, note that with operations, we can make the final string at most contain 1 zero (could have a string of all 1\'s, in which case we can do nothing, or have a single zero then all 1\'s, same situation). \n\nThis leads to the second realization, which is that if we do not have at least 2 zeroes, we are in fact already maximized (either it\'s one zero and all ones, or a 1 followed by some number of 1s, a zero, and then some number of 1s, in which case any switch is in fact worse) \n\nLooking at the first example (in comments), note that we can in fact group all of the zeroes on the left -> 0000111 (did not show in walk through, but it is in fact possible) \n\nThis means we can isolate the zeros before the switch process takes place \nHow many should we do then? \n\nBased on our answer above to switching zeros, one less than the total number of zeroes! This means we will \n\n- Find unconverted portion as the binary string up to the first zero (leave leading 1\'s alone) \n- Find the number of converted zeroes (one less than total number of zeroes) \n- Find the number of remaining zeroes -> there\'s only 1 \n- Find the number of non-leading-ones -> length of string less first zero (how much unconverted actually is) less the number of zeroes (how many already accounted for) \n- Build string as unconverted portion + number of converted zeroes + a single 0 + number of non leading ones -> this is your answer \n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nGet length of string \nGet number of zeros \nif less than two zeroes -> return binary \notherwise, build as outlined in intuition and return converted string \n\n# Complexity\n- Time complexity : O(n) \n    - O(n) to get number of zeros and first zero index  \xA0\n\n- Space complexity : O(n) stores final binary string \n\n# Code\n```\nclass Solution:\n    def maximumBinaryString(self, binary: str) -> str:\n        # binary string is binary \n        # if number contains 00 -> can replace with 10 \n        # if number contains 10 -> can replace with 01 \n        # return maximum binary string you can obtain after any number of operations \n        # 000110 \n        # 100110 # do any 00 first \n        # 110110 # no 00, but 10 at back. Try doing 10 at back and search for improvement. \n        # 110101 # no 00 but 10 at back. Try doing 10 at back and search for improvement. \n        # 110011 # do any 00 first. \n        # 111011 # no 00, but 10 at back. Try doing 10 at back and search for improvement. \n        # 110111 # no 00, but 10 at back. Try doing 10 at back and search for improvement. \n        # 101111 # no 00, but 10 at back. Try doing 10 at back and search for improvement. \n        # 011111 # no 00, no 10, stop, recurse backwards. Report best found along the way. \n        # hint 1 -> note with operations, can make the string only contain at most 1 zero \n        # hint 2 -> less than 2 zeros in input string, return it \n        #   python -> string.count(char, start, end) \n        bL = len(binary)\n        num_zeroes = binary.count(\'0\', 0, bL)\n        if num_zeroes < 2 : \n            return binary \n        else : \n            # hint 3 -> through operations all 0\'s can be grouped while pushing 1\'s down \n            #        -> means you can always convert all but 1 zero into a 1 \n            # hint 4 -> how far to the left should we push the zeros? leftmost 0 should never be \n            #        -> pushed further to the left as that would just knock out 1\'s already higher up \n            # hint 5 -> considering length of string can be large, time efficient way to construct output? \n            #        -> \n            # taken together, can group all 0\'s, then get length of zeros \n            # with length of zeros take one less. At this index less one should be a zero \n            # All others should be ones \n            # get the leftmost index of zero as we read left to right \n            zero_index = binary.index(\'0\') \n            # unconverted portion then is based on this index \n            unconverted_portion = binary[:zero_index]\n            # we can convert num_zeroes less 1 to 1\'s \n            converted_zeroes = \'1\' * (num_zeroes - 1) \n            # we will have at most 1 remaining zeroes \n            remaining_zeroes = \'0\'  \n            # we will have some non leading ones -> length of string less first index of zero less number of zeros -> cannot be negative \n            number_of_non_leading_ones = bL - zero_index - num_zeroes\n            if number_of_non_leading_ones < 0 : \n                number_of_non_leading_ones = 0 \n            unconverted_ones = \'1\' * number_of_non_leading_ones \n            # build converted string in order of operations final form \n            converted_string = unconverted_portion + converted_zeroes + remaining_zeroes + unconverted_ones \n            # return converted string \n            return converted_string\n\n```
['Python3']