Largest Odd Number in String: Right-to-Left Scan

Some problems look like they require heavy number parsing, but they fold down to a single observation about digits. LeetCode 1903 is one of those. Once you see the connection between odd numbers and their last digit, the solution writes itself.

The problem

LeetCode 1903: Largest Odd Number in String. You are given a string num that represents a large integer. Return the largest-valued odd number that is a non-empty substring of num, or an empty string "" if no odd number exists.

A substring is a contiguous sequence of characters within the string.

• num = "52" returns "5"
• num = "4206" returns ""
• num = "35427" returns "35427"

The key insight: oddness lives in the last digit

A number is odd if and only if its last digit is odd. That means the largest odd substring must end at the rightmost odd digit. Why? Because any substring that starts at index 0 and extends further to the right is a larger number (it has more digits). So the optimal strategy is to find the rightmost odd digit and return everything from the beginning of the string through that digit.

If you scan from right to left and find an odd digit at index i, the answer is num[0..i] (inclusive). If no odd digit exists anywhere in the string, the answer is "".

This greedy approach works because:

1. Substrings starting at index 0 are always larger than or equal to substrings starting at a later index (assuming equal or greater length).
2. You want the longest possible prefix that ends on an odd digit.
3. The rightmost odd digit gives you the longest such prefix.

Visual walkthrough

The code

def largest_odd_number(num: str) -> str:
    for i in range(len(num) - 1, -1, -1):
        if int(num[i]) % 2 == 1:
            return num[:i + 1]
    return ""

The loop starts at the last index and walks backward. At each position, it checks whether the digit is odd by computing int(num[i]) % 2. The moment it finds an odd digit, it returns the prefix num[:i + 1], which is every character from index 0 through index i.

If the loop completes without finding any odd digit, every digit in the string is even. In that case, no odd substring exists, so the function returns an empty string.

Notice that this approach works even for very large numbers. Because num is a string, you never need to parse the full value into an integer. You only convert one character at a time.

Complexity analysis

In the best case, the last digit itself is odd, and you return immediately in O(1). In the worst case, every digit is even, and you scan the entire string before returning "".

The building blocks

1. Right-to-left scanning. When the answer depends on the rightmost occurrence of some property, scanning from the end is the natural direction. This avoids processing characters you will never need.

2. Digit parity check. A number is odd if and only if its last digit is odd (1, 3, 5, 7, or 9). This property lets you reduce a question about an entire number to a question about a single digit.

3. Greedy prefix selection. The largest numeric substring starting from index 0 is always the longest one. By finding the farthest-right valid endpoint, you maximize the result in a single pass.

Edge cases

• All digits are even. num = "2468" has no odd digits. The loop finishes without returning, so the answer is "".
• Last digit is odd. num = "35427" ends with 7, which is odd. The very first check finds it, and the answer is the entire string.
• Single digit, odd. num = "9" returns "9" immediately.
• Single digit, even. num = "4" returns "" because the only digit is even.
• Leading zeros in the result are fine. The problem says num does not have leading zeros, but there is no constraint on the output being "canonical." Since the input itself has no leading zeros, any prefix of it also has no leading zeros.

From understanding to recall

This problem is a quick solve once you see the trick, but that is exactly what makes it tricky to remember. Easy problems have a way of blending together in your head. Two weeks from now, you might confuse this with another digit-scanning problem and waste time rediscovering the insight.

Spaced repetition fixes that. Instead of re-reading the full write-up, you drill the core building blocks: right-to-left scan, digit parity, greedy prefix. Each rep takes seconds, and after a few cycles spread across days, the pattern is locked in long-term memory.

When you see a similar problem in a contest or interview, the pieces click into place automatically. You do not have to rederive anything.

Related posts

• Palindrome Number - Another problem using digit properties
• Length of Last Word - Right-to-left string scanning
• Add Strings - Working with digit strings