Maximum Odd Binary Number - LeetCode Daily Challenge

Problem Statement

You are given a binary string s that contains at least one '1'.

You have to rearrange the bits in such a way that the resulting binary number is the maximum odd binary number that can be created from this combination.

Return a string representing the maximum odd binary number that can be created from the given combination.

Note that the resulting string can have leading zeros.

Example 1

Input: s = "010"
Output: "001"
Explanation: Because there is just one '1', it must be in the last position. So the answer is "001".

Example 2

Input: s = "0101"
Output: "1001"
Explanation: One of the '1's must be in the last position. The maximum number that can be made with the remaining digits is "100". So the answer is "1001".

Try here before watching the video.

Video Solution

Java Code

class Solution {
    public String maximumOddBinaryNumber(String s) {
        char[] arr = s.toCharArray();
        int left = 0, right = arr.length - 1;

        while(left <= right) {
            if(arr[left] == '1') {
                left += 1;
            }

            if(arr[right] == '0') {
                right -= 1;
            }

            if(left < right && arr[left] == '0' && arr[right] == '1') {
                arr[left] = '1';
                arr[right] = '0';
            }
        }

        arr[left - 1] = '0';
        arr[arr.length - 1] = '1';

        return new String(arr);
    }
}

C++ Code

class Solution {
public:
    string maximumOddBinaryNumber(string& s) {
        int left = 0, right = s.size() - 1;

        while (left <= right) {
            if (s[left] == '1') {
                left += 1;
            }

            if (s[right] == '0') {
                right -= 1;
            }

            if (left < right && s[left] == '0' && s[right] == '1') {
                s[left] = '1';
                s[right] = '0';
            }
        }

        s[left - 1] = '0';
        s[s.size() - 1] = '1';

        return s;
    }
};

Python Code

class Solution:
    def maximumOddBinaryNumber(self, s: str) -> str:
        arr = list(s)
        left, right = 0, len(arr) - 1

        while left <= right:
            if arr[left] == '1':
                left += 1

            if arr[right] == '0':
                right -= 1

            if left < right and arr[left] == '0' and arr[right] == '1':
                arr[left] = '1'
                arr[right] = '0'

        arr[left - 1] = '0'
        arr[-1] = '1'

        return ''.join(arr)

Javascript Code

var maximumOddBinaryNumber = function(s) {
    let arr = s.split('');
    let left = 0, right = arr.length - 1;

    while (left <= right) {
        if (arr[left] === '1') {
            left += 1;
        }

        if (arr[right] === '0') {
            right -= 1;
        }

        if (left < right && arr[left] === '0' && arr[right] === '1') {
            arr[left] = '1';
            arr[right] = '0';
        }
    }

    arr[left - 1] = '0';
    arr[arr.length - 1] = '1';

    return arr.join('');
};

Go Code

func maximumOddBinaryNumber(s string) string {
    arr := []rune(s)
    left, right := 0, len(arr)-1

    for left <= right {
        if arr[left] == '1' {
            left++
        }

        if arr[right] == '0' {
            right--
        }

        if left < right && arr[left] == '0' && arr[right] == '1' {
            arr[left] = '1'
            arr[right] = '0'
        }
    }

    arr[left-1] = '0'
    arr[len(arr)-1] = '1'

    return string(arr)
}

Complexity Analysis

Time Complexity: O(N), as we are iterating through the entire string.
Space Complexity: O(N) or O(1), it depends, like in C++, we are not creating a new string but making changes in the same string because strings are mutable in C++ whereas in Java, Python, Javascript, Golang strings are immutable. Due to the immutable behavior of string, we need to create a new array or list of characters in these languages which would take O(N).