Largest Odd Number in String — Solution

Problem

You are given a string of digits representing a non-negative integer. Find the largest odd number that can be formed by taking a non-empty prefix of that string, and return it as a string. If no odd prefix exists, return an empty string.

• Input: num = "35427"
• Output: "35427"
• Explanation: The full number ends in 7, which is odd, so the entire string is the largest valid prefix.

Counter-example: "4206" → "" because every prefix ends in an even digit (6, 0, 2, or 4).

Intuition

An integer is odd if and only if its last digit is odd. Since a longer prefix always represents a larger number (more digits), the optimal strategy is to find the rightmost odd digit — that gives us the longest prefix that is still an odd number. We scan from the right and return the prefix ending at the first odd digit we find.

Solution — Right-to-Left Scan

Walk the string backwards until you hit an odd digit. Return the prefix up to and including that position.

1. Start at the last character and move left.
2. For each character, check whether its digit value is odd (digit % 2 == 1).
3. On the first odd digit found, return the prefix from index 0 through that index (inclusive).
4. If the entire string was scanned without finding an odd digit, return "".

1def largestOddNumber(num: str) -> str:
2    for i in range(len(num) - 1, -1, -1):
3        if int(num[i]) % 2 == 1:  # odd digit found — this is the cut point
4            return num[:i + 1]
5    return ""

Time: O(n) — single pass through at most n characters.

Space: O(1) extra — the returned substring is the output, not auxiliary storage.

Complexity Summary

Common Mistakes

• Off-by-one on the substring bound: returning num[:i] instead of num[:i+1] — the odd digit at index i must be included in the result, otherwise you return a prefix that ends one position too early.
• Converting the whole string to an integer: numbers up to 10⁵ digits long overflow any primitive type; the digit parity check only needs the last character, never the full numeric value.
• Scanning left to right and returning the first odd prefix: this gives the shortest odd prefix (e.g. "5" from "52"), not the largest. Scanning right to left gives the longest prefix with an odd final digit, which is always the numerically largest.
• Forgetting the all-even case: if no odd digit exists anywhere, the loop exits without returning — make sure to explicitly return "" after the loop.
• Using num[i] % 2 instead of (num[i] - '0') % 2 in Java/C++: num[i] in those languages is a char, not an int; its ASCII value is not the same as its digit value, so the modulo check would be wrong.

Related Problems

• reverse-integer — digit-by-digit number manipulation using modulo and division
• palindrome-number — determining a numeric property by inspecting individual digits
• largest-number — arranging digits/numbers in a string to maximize a numeric value
• plus-one — right-to-left digit traversal with carry propagation
• find-numbers-with-even-number-of-digits — digit counting and property checking on numeric values