To solve Largest Odd Number in String, iterate from the end to find the rightmost odd digit, then slice the string to that position. This guarantees the largest odd value because removing trailing even digits preserves maximum value. If no odd digit exists, return an empty string immediately.
Problem Statement
You are given a string num representing a large integer. Your task is to return the largest-valued odd integer substring, or an empty string if none exists. Substrings are contiguous sequences of characters within num, and the solution must handle strings up to 105 characters efficiently.
For example, given num = "52", the substrings are "5", "2", and "52", with "5" being the largest odd. If num = "4206", no odd substrings exist, so return "". If num = "35427", the entire string is already an odd number and is returned as is.
Examples
Example 1
Input: num = "52"
Output: "5"
The only non-empty substrings are "5", "2", and "52". "5" is the only odd number.
Example 2
Input: num = "4206"
Output: ""
There are no odd numbers in "4206".
Example 3
Input: num = "35427"
Output: "35427"
"35427" is already an odd number.
Constraints
- 1 <= num.length <= 105
- num only consists of digits and does not contain any leading zeros.
Solution Approach
Greedy Backward Scan
Start from the last character and move leftward until the first odd digit is found. Slice the string up to and including this digit to get the largest odd number.
Invariant Validation
Ensure that slicing does not skip any potential larger odd substrings. Only the rightmost odd digit guarantees the maximal substring, maintaining the invariant that all digits to the right are less significant.
Edge Case Handling
If no odd digit is found after scanning the entire string, return an empty string. This handles inputs with only even digits like "4206" and preserves correctness.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | O(n) |
| Space | O(1) |
The solution scans each digit once, giving O(n) time complexity, and uses constant extra space for slicing and character inspection, resulting in O(1) space complexity.
What Interviewers Usually Probe
- Asks about scanning from left vs right and why greedy works here
- Mentions handling extremely long numeric strings efficiently
- Probes understanding of odd/even digit significance for substring selection
Common Pitfalls or Variants
Common pitfalls
- Checking every possible substring leads to O(n^2) time complexity, which is unnecessary
- Returning the first odd digit from the start instead of the last may produce a smaller number
- Forgetting to return empty string when no odd digit exists
Follow-up variants
- Find the smallest odd substring instead of the largest
- Allow non-contiguous digits but still maximize odd value
- Handle strings with leading zeros or negative signs
How GhostInterview Helps
- Guides you to iterate digits correctly with the greedy pattern
- Highlights invariant checks to avoid incorrect substrings
- Points out edge cases like strings without odd digits efficiently
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
How do I find the largest odd number in a string efficiently?
Scan from the end to find the last odd digit, then return the substring up to that point.
Why is a greedy backward scan the right pattern for this problem?
Because the last odd digit ensures the maximal substring value, preserving all higher digits on the left.
What if the string contains only even digits?
Return an empty string, as no odd substring exists.
Can I iterate from left to right instead?
Left-to-right requires extra logic to track potential maximal odd substrings; right-to-left guarantees the correct result directly.
How does invariant validation apply here?
It ensures that slicing at the last odd digit always produces the largest odd substring without missing higher digits to the left.
Need direct help with Largest Odd Number in String instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Largest Odd Number in String from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Determine if Alice can force a win in the Sum Game by strategically replacing '?' using a greedy and invariant approach.
Open problem page#2038 Remove Colored Pieces if Both Neighbors are the Same ColorAlice and Bob play a game removing colored pieces; Alice wins if she makes the last valid move.
Open problem page#1247 Minimum Swaps to Make Strings EqualThis problem requires determining the minimum number of swaps to make two strings equal by swapping characters between the strings.
Open problem page