Code Implementation

class Solution:
    def largestOddNumber(self, num: str) -> str:
        # Start from the rightmost digit and move left
        for i in range(len(num) - 1, -1, -1):
            if int(num[i]) % 2 == 1:
                return num[:i+1]
        return ""
      

class Solution {
public:
    string largestOddNumber(string num) {
        for (int i = num.size() - 1; i >= 0; --i) {
            if ((num[i] - '0') % 2 == 1) {
                return num.substr(0, i + 1);
            }
        }
        return "";
    }
};
      

class Solution {
    public String largestOddNumber(String num) {
        for (int i = num.length() - 1; i >= 0; --i) {
            if ((num.charAt(i) - '0') % 2 == 1) {
                return num.substring(0, i + 1);
            }
        }
        return "";
    }
}
      

var largestOddNumber = function(num) {
    for (let i = num.length - 1; i >= 0; --i) {
        if (parseInt(num[i]) % 2 === 1) {
            return num.slice(0, i + 1);
        }
    }
    return "";
};
      

Problem Description

Given a string num representing a large non-negative integer, you are asked to find the largest-valued odd integer (as a substring) that is a non-empty prefix of num. In other words, you should return the longest prefix of num that forms an odd number. If no such odd-valued prefix exists, return an empty string "".

• Each character in num is a digit ('0'-'9').
• You cannot rearrange or remove digits except by shortening the string from the right.
• You must not skip any digits: the answer must be a prefix (i.e., it starts at the first character).
• There is always exactly one valid answer for each input.

Thought Process

At first glance, you might consider checking every possible prefix of num to see if it forms an odd number, but this could be inefficient for long strings. Instead, notice that the only thing that determines if a number is odd is its last digit. Therefore, to find the largest odd prefix, you only need to look for the rightmost odd digit in the string. Once you find it, the prefix ending at that digit is the answer.

This insight allows us to avoid generating all possible prefixes or doing any unnecessary calculations. We can simply scan the string backwards, checking each digit, and as soon as we find an odd digit, we return the prefix up to that point.

Solution Approach

Let's break down the solution step by step:

1. Start from the rightmost digit: Since the prefix must be as long as possible, we want to include as many digits as possible, but the number must end with an odd digit.
2. Scan backwards: Loop from the last digit to the first, checking if each digit is odd (i.e., the digit modulo 2 is 1).
3. Return the prefix: As soon as you find an odd digit, return the substring from the start up to and including this digit. This is the largest possible odd number prefix.
4. If no odd digit is found: If you finish the loop without finding any odd digit, return an empty string as there is no valid odd prefix.

This approach is efficient because it only requires a single pass through the string, and it does not require any extra data structures.

Example Walkthrough

Let's use the input num = "35420" as an example.

1. Start from the rightmost digit: '0'. Is it odd? No.
2. Move left to '2'. Is it odd? No.
3. Move left to '4'. Is it odd? No.
4. Move left to '5'. Is it odd? Yes (5 % 2 == 1).
5. Since '5' is odd, return the prefix up to this digit: "3545", but since '5' is at index 1 (0-based), the prefix is "354". Wait, let's double-check: the prefix should include up to index 3, so the substring is num[:4] which is "3542". But '2' is not odd; the correct index is 1 (0-based), so the prefix is num[:2] which is "35". But let's clarify:
   • Index 4: '0' (not odd)
   • Index 3: '2' (not odd)
   • Index 2: '4' (not odd)
   • Index 1: '5' (odd) → return num[:2] which is "35"
   So the answer is "35".
6. If there were no odd digits, the answer would be "".

Time and Space Complexity

• Brute-force approach: Checking every prefix and testing if it's odd would take O(N^2) time for a string of length N, since extracting each prefix and converting it to a number is O(N) and there are O(N) prefixes.
• Optimized approach (current solution): We only scan the string from right to left once, so the time complexity is O(N), where N is the length of num.
• Space complexity: Both approaches use O(1) extra space, since we are not using any additional data structures (just returning a substring).

Summary

The key insight for solving the "Largest Odd Number in String" problem is recognizing that whether a number is odd depends only on its last digit. By scanning the string from right to left and looking for the rightmost odd digit, we can efficiently find the largest odd prefix in a single pass. This makes the solution both simple and optimal, requiring only O(N) time and O(1) extra space.