#2864

Easy

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Maximum Odd Binary Number

Rearrange a binary string to form the largest odd binary number using a greedy approach and least significant bit validation.

math string greedy

Problem Statement

Given a binary string s containing at least one '1', rearrange the bits so that the resulting binary number is odd and as large as possible. You must return a string representing this maximum odd binary number.

Each '1' except for the one at the least significant position can be freely rearranged to maximize the number. The string contains only '0's and '1's, and its length ranges from 1 to 100.

Examples

Example 1

Input: s = "010"

Output: "001"

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"

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

Constraints

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

Solution Approach

Count and Isolate Last '1'

Count all '1's in the string. Reserve one '1' for the least significant position to satisfy the odd number constraint.

Greedy Placement of Remaining Bits

Place all remaining '1's to the left in the string followed by all '0's. This greedy placement ensures the largest binary value before the final '1'.

Combine and Return

Append the reserved '1' at the end. Concatenate the arranged '1's, '0's, and the final '1' to form the maximum odd binary string and return it.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

The algorithm scans the string once to count '1's and then constructs the result in a single pass, resulting in O(n) time and O(n) space complexity.

What Interviewers Usually Probe

Ask why placing a '1' at the end guarantees an odd number.
Check if candidates correctly separate the last '1' from the remaining bits.
Expect explanation of greedy choice for maximizing the binary value.

Common Pitfalls or Variants

Common pitfalls

Forgetting to reserve one '1' at the least significant position, producing an even number.
Reordering '0's and '1's incorrectly, reducing the maximum value.
Assuming multiple '1's can occupy the last position, violating the odd constraint.

Follow-up variants

Find the maximum even binary number by placing '0' at the least significant bit.
Count the number of maximum odd binary numbers possible from the same string.
Extend the problem to ternary strings with a similar odd-value constraint.

FAQ

What is the key pattern in Maximum Odd Binary Number?

The key pattern is a greedy choice with invariant validation: place one '1' at the end and maximize remaining bits.

Can the last bit be '0' in the maximum odd binary number?

No, the last bit must be '1' to ensure the number is odd.

How do I handle strings with only one '1'?

Place that '1' at the end; all preceding bits are '0's, forming the correct maximum odd binary number.

What is the time complexity of the optimal solution?

It is O(n) because counting and arranging bits requires a single pass through the string.

Does the order of '0's matter in the solution?

Yes, '0's should follow all '1's except the reserved last '1' to maximize the binary value.

terminal

Solution

Solution 1: Greedy

First, we count the number of '1's in the string $s$, denoted as $cnt$. Then, we place $cnt - 1$ '1's at the highest position, followed by the remaining $|s| - cnt$ '0's, and finally add one '1'.

1

2

3

4

class Solution:
    def maximumOddBinaryNumber(self, s: str) -> str:
        cnt = s.count("1")
        return "1" * (cnt - 1) + (len(s) - cnt) * "0" + "1"

Continue Practicing

#2844 minimum operations to make a special number #2842 count k subsequences of a string with maximum beauty #3014 minimum number of pushes to type word i