The Largest Odd Number in String coding problem asks you to find the largest valued odd integer that exists as a non-empty substring of a given string of digits. If no odd number can be formed, you should return an empty string. Since we are looking for the largest value, we are essentially looking for the longest prefix that ends with an odd digit.
This is a frequent question at companies like Microsoft and Meta because it tests fundamental string manipulation and mathematical logic. It’s a great example of how a seemingly complex "search" problem can be solved with a very simple greedy observation. Interviewers want to see if you can identify that any number's "oddness" is determined solely by its last digit.
This problem uses the Math, String, and Greedy interview pattern. To find the largest odd number, we should include as many of the leading digits as possible. Therefore, the strategy is to iterate from the end of the string (the right side) toward the beginning. The first time we encounter an odd digit ('1', '3', '5', '7', or '9'), the entire substring from the start of the string to that digit is our answer.
Input string: "4206".
Input string: "3542".
The most common mistake is trying to generate all possible substrings and checking each one for "oddness," which results in O(N²) or O(N³) complexity. Another mistake is forgetting that leading zeros in the substring are allowed as long as the original string had them. Some candidates also overcomplicate the math by trying to convert the entire string into a BigInt before checking.
In "String, Greedy interview pattern" questions, always look for the "terminating condition." In this case, the last digit of the number determines its parity. Once you realize this, the problem transforms from a complex search into a simple reverse-order scan.
