#1903

Easy

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Largest Odd Number in String

Find the largest odd number in a string using a greedy approach with careful digit inspection and invariant checks.

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

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.

terminal

Solution

Solution 1: Reverse Traversal

We can traverse the string from the end to the beginning, find the first odd number, and then return the substring from the beginning to this odd number. If there is no odd number, return an empty string.

1

2

3

4

5

6

class Solution:
    def largestOddNumber(self, num: str) -> str:
        for i in range(len(num) - 1, -1, -1):
            if (int(num[i]) & 1) == 1:
                return num[: i + 1]
        return ''

Continue Practicing

#1927 sum game #2038 remove colored pieces if both neighbors are the same color #1247 minimum swaps to make strings equal