Maximum Binary String After Change

## Quick Links

Problem Description

Ah, the classic “Maximum Binary String After Change” problem! It’s like trying to make the best sandwich ever, but you can only use certain ingredients and you have to follow some weird rules. Imagine you have a binary string (a string made up of 0s and 1s) and you want to make it as “maximum” as possible.

In this case, “maximum” means you want to turn as many leading bits into 1s as you can, but there’s a catch! You can only change a 0 to a 1 if it’s the last 0 in a sequence of 1s. So, if you have a string like 100110, you can’t just go around changing 0s to 1s willy-nilly. You have to follow the rules, just like how you can’t eat dessert before dinner (but we all know that’s a lie).

Code Solution


class Solution:
    def maximumBinaryString(self, binary: str) -> str:
        zeros = binary.count('0')
        prefixOnes = binary.find('0')

        ans = ['1'] * len(binary)

        if prefixOnes != -1:
            ans[prefixOnes + zeros - 1] = '0'
        return ''.join(ans)

Approach

The approach here is quite straightforward. First, we count the number of zeros in the binary string. Then, we find the position of the first zero. We create a new list filled with 1s, and if there’s a zero in the original string, we replace the last zero with a 0 in our new list. Finally, we join the list back into a string and return it. Simple, right? Just like making a sandwich, but with fewer crumbs!

Time and Space Complexity

Time Complexity: O(n), where n is the length of the binary string. We traverse the string a couple of times, but it’s all linear, baby!

Space Complexity: O(n) as well, since we create a new list to store our result.

Real-World Example

Imagine you’re at a party, and you want to be the life of it. You start with a group of friends (the binary string), and you want to make sure everyone is having a good time (turning 0s into 1s). But you can only invite more friends (turn 0s into 1s) if you have a solid group already (the leading 1s). So, you strategically invite the last friend in the group to keep the party going. That’s basically what this problem is about!