Largest Odd Number in String — Problem & Solution
Largest Odd Number in String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Largest Odd Number in String is an easy coding problem on strings, math and greedy, asked in Amazon and Adobe interviews.
- Difficulty: Easy
- Topics: Strings, Math, Greedy
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a string num of digits. Return the largest-valued odd integer that is a non-empty substring of num, as a string.
If no odd substring exists, return the empty string.
Example 1
Input: num = "52"
Output: 5
Explanation: The only odd substring is "5".
Example 2
Input: num = "4206"
Output:
Explanation: Every digit is even.
Example 3
Input: num = "35427"
Output: 35427
Explanation: The whole string is already odd.
Constraints
1 <= num.length <= 100000num consists of digits only and has no leading zeros.
Hints for Largest Odd Number in String
Hint 1
A number is odd exactly when its last digit is odd.
Hint 2
To make the value as large as possible, keep the prefix as long as possible.
Hint 3
So scan from the right for the last odd digit and return everything up to and including it.
How to solve Largest Odd Number in String
Any odd substring must end at an odd digit. Among substrings ending at a fixed position, the longest — the whole prefix — is the largest, and a longer prefix always beats a shorter one for a digit string with no leading zeros.
Approach
- Scan
numfrom the last index backwards. - At the first odd digit found at index
i, returnnum[0..i]. - Return the empty string if no odd digit exists.
Why it works
Extending a substring leftward can only increase its value (it adds more significant digits), so the best choice ends at the rightmost odd digit and starts at index 0.
Complexity
- Time —
O(n) - Space —
O(n) for the returned prefix
Pitfalls
- Searching for the largest odd digit rather than the rightmost one gives a shorter, smaller answer.
- Enumerating substrings is O(n²) and hopeless at 100,000 characters.
- The answer keeps any interior zeros — only leading zeros would be a problem, and the input has none.
Reference solution
Python
def largestOddNumber(num: str) -> str:
for i in range(len(num) - 1, -1, -1):
if int(num[i]) % 2 == 1:
return num[:i + 1]
return ""Java
public static 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 "";
}C++
string largestOddNumber(string num) {
for (int i = (int) num.size() - 1; i >= 0; i--) {
if ((num[i] - '0') % 2 == 1) return num.substr(0, i + 1);
}
return "";
}JavaScript
var largestOddNumber = function(num) {
for (let i = num.length - 1; i >= 0; i--) {
if ((num.charCodeAt(i) - 48) % 2 === 1) return num.slice(0, i + 1);
}
return "";
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Greedy Algorithms