Maximum Binary String After Change — LeetCode 1702 Python Solution

The problem

You are given a binary string binary consisting of only 0's or 1's. You can apply each of the following operations any number of times: Operation 1: If the number contains the substring "00", you can replace it with "10".

Example

Input

binary = "000110"

Output

"111011"

Explanation

A valid transformation sequence can be:

Python solution

class Solution:
    def maximumBinaryString(self, binary: str) -> str:
        k = binary.find('0')
        if k == -1:
            return binary
        k += binary[k + 1 :].count('0')
        return '1' * k + '0' + '1' * (len(binary) - k - 1)

Complexity

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 1702. Maximum Binary String After Change is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Greedy.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Related problems