Python O(n) with explanation
Thinking about the rules for a moment, we notice:\n\n- The number of ones in the string can only increase; there are only two ways to\n  change substrings and n
Thinking about the rules for a moment, we notice:\n\n- The number of ones in the string can only increase; there are only two ways to\n  change substrings and neither decreases the number of ones\n- If we have a continuous substring of zeros, we can change all but the last\n  zero to ones by repeatedly applying rule 1.\n- We can bubble existing ones down to the end of the string with rule 2.\n  \'**10**00\' -> \'0**10**0\' -> \'00**10**\' -> \'0001\'.\n\nCombining these, we can see that our final string should only contain one zero.\nThis is because we can bubble as many ones as necessary to the end, and then\nhave the zeros in a nice row to change into ones again.\n\nJust following this naiive strategy of bubbling ones to the end and changing\nzeros is a bit overzealous though. To get the largest number, we want the final\nzero to be as close to the end as possible. This can be done by not bubbling \nany leading ones, and then applying the naiive solution to the remaining\nsubstring.\n\n```python\ndef maximumBinary(binary):\n  if "0" not in binary:\n    return binary\n  \n  front = binary.index("0")\n  \n  count = Counter(binary[front:])\n  \n  return "1" * (front + count["0"] - 1) + "0" + "1" * count["1"]\n```\n\nThe time complexity will be O(n), and the space complexity will be O(n) due to\nthe array slice we made. (We could make it O(1) by using `islice(binary, front,\nNone)` or similar, but I think the slice is easier to read)\n\n
[]