Largest Odd Number in String - Solution & Explanation

Problem Overview: You are given a numeric string num. The task is to return the largest-valued odd number that can be formed as a substring. Since substrings keep the original order of digits, the largest valid odd number must be a prefix that ends at the rightmost odd digit.

Approach 1: Checking Last Odd Digit (Greedy) (Time: O(n), Space: O(1))

This approach relies on a simple observation: an integer is odd if its last digit is odd (1, 3, 5, 7, 9). To maximize the value of the substring, you want the longest prefix that ends with an odd digit. Iterate from the end of the string toward the beginning and check each digit. As soon as you find an odd digit, return the substring from index 0 to that position inclusive. The scan takes at most n steps and no extra data structures are required, making it an efficient greedy strategy working directly on the string.

Approach 2: Using Regular Expression (Time: O(n), Space: O(n))

Regular expressions can also identify the longest prefix that ends with an odd digit. A pattern such as ^\d*[13579] matches any sequence of digits starting from the beginning of the string and ending with an odd digit. The regex engine scans the string until it finds the last valid odd-ending prefix. While the theoretical time complexity is still O(n), regex introduces additional overhead and temporary allocations compared with direct iteration. This approach is convenient in scripting languages like Python or JavaScript but less common in interviews where explicit math checks on digits are clearer.

Recommended for interviews: The greedy scan from the end is the expected solution. It demonstrates that you recognize the defining property of odd numbers and avoid unnecessary substring generation. Interviewers typically look for this observation and an O(n) pass with constant space. Regex solutions are concise but hide the underlying reasoning and are rarely preferred during whiteboard discussions.