Max Odd Binary Number LeetCode 2864

LeetCode 2864 — Maximum Odd Binary Number — gives you a binary string s that is guaranteed to contain at least one "1". Your task is to rearrange the characters of s to form the maximum possible odd binary number and return that number as a string.

A binary number is odd if and only if its last (least significant) bit is 1. Maximizing a binary number means placing the highest-value bits as far left (most significant) as possible. These two requirements — oddness and maximum value — interact in a simple, elegant way that makes this a classic greedy problem.

The input string may contain any mix of "0"s and "1"s with at least one "1". You must use all characters exactly once. Constraints allow strings up to length 10⁵, so O(n) is the target complexity.

To maximize a binary number, we want as many 1s as possible in the most significant positions — that is, at the left end of the string. Each position k from the right contributes 2^k to the total value, so a 1 in position k is worth twice a 1 in position k-1. Packing 1s to the left is the only optimal strategy.

To ensure oddness, the last bit must be 1. So we must reserve exactly one "1" for the final position. All remaining 1s go to the front. Zeros fill the gap in between. This construction satisfies both constraints simultaneously and cannot be improved upon.

This is greedy at its most transparent: a single scan to count 1s and zeros, then direct construction. No sorting, no backtracking, no dynamic programming. The problem reduces to arithmetic on character counts.

The algorithm is a two-step process: count, then construct. Count the number of 1s in the string (ones = s.count("1") in Python). The number of zeros follows as zeros = len(s) - ones. Construct the result as "1" * (ones - 1) + "0" * zeros + "1".

This is O(n) time because counting the characters requires one pass and building the result string requires another. Space is O(n) for the output string. No extra data structures are needed.

The formula works for all valid inputs: if ones == 1, the result is zeros zeros followed by a single trailing 1 — the smallest possible odd number using those characters. If ones == len(s) (all 1s), the result is (len(s) - 1) leading 1s and a trailing 1, which is just all 1s reordered identically.

Binary value depends on position. The leftmost bit has the highest place value: position k from the right contributes 2^k. A 1 in the most significant position is worth more than all lower positions combined. Therefore, placing all available 1s as far left as possible is always optimal.

The trailing 1 is unavoidable — without it the number would be even. But it sits at position 0 (value 1), the least significant position. Any swap that moved this trailing 1 leftward would either create an even number (if we left a 0 at the end) or require moving a 1 from the left to the right (decreasing overall value). Neither helps.

No arrangement can outperform (ones-1) leading 1s + all zeros + trailing 1. We have used every available 1 in the highest possible positions while satisfying the oddness constraint. This greedy argument is tight: any deviation from this layout produces a strictly smaller or even number.

Consider s = "010". We have ones = 1, zeros = 2. Result = "1" * (1-1) + "0" * 2 + "1" = "" + "00" + "1" = "001". In decimal that is 1 — the only odd number we can form from one 1 and two 0s. Any other arrangement ("010" = 2, "100" = 4) is even, so "001" is the correct answer.

Consider s = "0101". We have ones = 2, zeros = 2. Result = "1" * 1 + "0" * 2 + "1" = "1001". In decimal that is 9. The other candidate arrangements that end in 1 include "0101" = 5 and "0011" = 3 and "1001" = 9. Our greedy picks 9, the maximum.

Both examples confirm the pattern: leading 1s first, zeros in the middle, trailing 1 at the end. The formula is deterministic and requires no comparison between candidate strings.

In Python, the solution is a one-liner: return "1" * (s.count("1") - 1) + "0" * s.count("0") + "1". For clarity, split into ones = s.count("1"); zeros = len(s) - ones; return "1" * (ones - 1) + "0" * zeros + "1". String repetition in Python is O(n), so the total time is O(n).

In Java, use StringBuilder: int ones = 0; for (char c : s.toCharArray()) if (c == "1") ones++; int zeros = s.length() - ones; StringBuilder sb = new StringBuilder(); for (int i = 0; i < ones - 1; i++) sb.append("1"); for (int i = 0; i < zeros; i++) sb.append("0"); sb.append("1"); return sb.toString(). Same O(n) time and O(n) space.

Time complexity is O(n) for both count and construction passes. Space complexity is O(n) for the output string. The solution handles all edge cases within the problem constraints: ones ≥ 1 is guaranteed, so ones - 1 ≥ 0 and the leading block is always valid.

Can Place Flowers (LeetCode 605) is another greedy problem on an array where you greedily place items in the earliest valid positions without checking globally — similar in spirit to greedily assigning 1s to the most significant positions here. Both problems have a single-pass greedy solution that is provably optimal.

Increasing Triplet Subsequence (LeetCode 334) uses greedy maintenance of two threshold values to detect a rising triplet without sorting — demonstrating how greedy strategies avoid expensive enumeration. Merge Strings Alternately (LeetCode 1768) constructs an output by greedy interleaving, similar to how we construct the binary result from counted parts.

The greedy construction family — where you count or classify characters and place them in optimal order — includes problems like Reorganize String, Task Scheduler, and Longest Palindrome. Maximum Odd Binary Number is among the simplest representatives: no frequency constraints, no cooldowns, just count and place. It is an ideal entry point for understanding greedy string construction.