2864. Maximum Odd Binary Number - Explanation

Problem Link

Description

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 = "0110"

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".

Example 2:

Input: s = "100"

Output: "001"

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

Constraints:

• 1 <= s.length <= 100
• s consists only of '0' and '1'.
• s contains at least one '1'.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Sorting

class Solution:
    def maximumOddBinaryNumber(self, s: str) -> str:
        s = sorted(s)
        s.reverse()
        i = len(s) - 1
        while i >= 0 and s[i] == "0":
            i -= 1

        s[i], s[len(s) - 1] = s[len(s) - 1], s[i]
        return ''.join(s)

Time & Space Complexity

• Time complexity: $O(n \log n)$
• Space complexity: $O(n)$

---

2. Greedy

class Solution:
    def maximumOddBinaryNumber(self, s: str) -> str:
        count = 0
        for c in s:
            if c == "1":
                count += 1

        return (count - 1) * "1" + (len(s) - count) * "0" + "1"

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

---

3. Two Pointers

class Solution:
    def maximumOddBinaryNumber(self, s: str) -> str:
        s = [c for c in s]
        left = 0

        for i in range(len(s)):
            if s[i] == "1":
                s[i], s[left] = s[left], s[i]
                left += 1
        s[left - 1], s[len(s) - 1] = s[len(s) - 1], s[left - 1]
        return "".join(s)

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$