Leetcode 1702. Maximum Binary String After Change

Problem Explanation

You are given a binary string consisting of only 0's and 1's. Your task is to apply two operations as many times as you want in any order to obtain the maximum binary string possible. The two operations are:

1. If the number contains the substring "00", you can replace it with "10".
2. If the number contains the substring "10", you can replace it with "01".

A binary string x is greater than binary string y if x's decimal representation is greater than y's decimal representation. You need to return the maximum binary string after applying the operations.

Let's walk through an example to understand better:

1Example:
2
3Input: binary = "000110"
4Output: "111011"
5
6Valid transformation sequence:
7"000110" -> "000101" (Operation 2)
8"000101" -> "100101" (Operation 1)
9"100101" -> "110101" (Operation 1)
10"110101" -> "110011" (Operation 2)
11"110011" -> "111011" (Operation 1)

Solution Explanation

In this solution, we will first find the number of zeros in the given binary string and note down the position of the first zero. Then we will replace the entire string with 1's. After that, we will place a single '0' at position (prefixOnes + zeros - 1) if there is at least one zero in the string. This operation will give us the maximum binary string that can be obtained after a certain number of operations.

Let's walk through the example for a better understanding:

1Input: binary = "000110"
2
3Step 1: Calculate zeros and prefixOnes:
4        zeros = 4 (Number of zeros in the string)
5        prefixOnes = 1 (Position of first zero)
6
7Step 2: Replace the entire string with 1's:
8        binary = "111111"
9
10Step 3: Place a single '0' at position:
11        (prefixOnes + zeros - 1) = (1 + 4 - 1) = 4
12        binary[4] = '0'
13        binary = "111011"
14
15Output: "111011" (This is the maximum binary string for the given input)

Now, let's implement this solution in different programming languages.

C++ Solution

1#include <algorithm>
2#include <string>
3using namespace std;
4
5class Solution {
6 public:
7  string maximumBinaryString(string binary) {
8    const int zeros = count(begin(binary), end(binary), '0');
9    const int prefixOnes = binary.find('0');
10
11    binary.assign(binary.length(), '1');
12
13    if (prefixOnes != string::npos)
14      binary[prefixOnes + zeros - 1] = '0';
15
16    return binary;
17  }
18};

Java Solution

1import java.util.*;
2
3class Solution {
4    public String maximumBinaryString(String binary) {
5        int zeros = 0;
6        int prefixOnes = -1;
7        
8        for (int i = 0; i < binary.length(); ++i) {
9            if (binary.charAt(i) == '0') {
10                zeros++;
11                if (prefixOnes == -1)
12                    prefixOnes = i;
13            }
14        }
15        
16        char[] chars = new char[binary.length()];
17        Arrays.fill(chars, '1');
18        
19        if (prefixOnes != -1)
20            chars[prefixOnes + zeros - 1] = '0';
21        
22        return new String(chars);
23    }
24}

JavaScript Solution

1class Solution {
2    maximumBinaryString(binary) {
3        const zeros = binary.split('').filter(c => c === '0').length;
4        let prefixOnes = binary.indexOf('0');
5
6        binary = binary.split('').map(_ => '1').join('');
7
8        if (prefixOnes !== -1)
9            binary = binary.substring(0, prefixOnes + zeros - 1) + '0' + binary.substring(prefixOnes + zeros);
10
11        return binary;
12    }
13}

Python Solution

1class Solution:
2    def maximumBinaryString(self, binary: str) -> str:
3        zeros = binary.count('0')
4        prefixOnes = binary.find('0')
5
6        binary = '1' * len(binary)
7
8        if prefixOnes != -1:
9            binary = binary[:prefixOnes + zeros - 1] + '0' + binary[prefixOnes + zeros:]
10
11        return binary

C# Solution

1using System;
2
3public class Solution {
4    public string MaximumBinaryString(string binary) {
5        int zeros = 0;
6        int prefixOnes = -1;
7        
8        for (int i = 0; i < binary.Length; ++i) {
9            if (binary[i] == '0') {
10                zeros++;
11                if (prefixOnes == -1)
12                    prefixOnes = i;
13            }
14        }
15        
16        char[] chars = new char[binary.Length];
17        Array.Fill(chars, '1');
18        
19        if (prefixOnes != -1)
20            chars[prefixOnes + zeros - 1] = '0';
21        
22        return new string(chars);
23    }
24}

In the solutions above, we first calculate the number of zeros and the position of the first zero. Then, we replace the entire string with 1's, and if there is at least one zero in the string, we place a single '0' at position (prefixOnes + zeros - 1).We can measure the time complexity of the code by analyzing the number of operations performed by the code. The time complexity of the function is mainly determined by these parts:

1. Counting the number of zeros and finding the position of the first zero: O(N).
2. Replacing the entire string with 1's: O(N) (For example, in JavaScript, Array.fill() function has a time complexity of O(N) and in other languages, it is not more than O(N).)
3. Replacing one character with a '0': O(1) (This operation is constant and does not depend on the length of the string.)

By combining these complexities, the total time complexity of the function will be O(N + N + 1) = O(2N + 1) = O(N), where N is the length of the input binary string.

The overall time complexity of the function is O(N), which is linear with respect to the length of the input binary string. It shows that the given solution is efficient in terms of time complexity.