LeetCode 1903 - Largest Odd Number in String

The problem asks us to find the largest-valued odd integer substring from a given string num that represents a large integer. Here, a substring is any contiguous sequence of characters in num.

leetcodeeasymathstringgreedy

LeetCode Problem 1903

Difficulty: 🟢 Easy
Topics: Math, String, Greedy

Solution

Problem Understanding

The problem asks us to find the largest-valued odd integer substring from a given string num that represents a large integer. Here, a substring is any contiguous sequence of characters in num. We must return the substring itself as a string, or an empty string if no odd number exists in num.

For example, if num = "35427", the entire string itself is already an odd number because its last digit 7 is odd. For num = "4206", none of the digits are odd, so no odd number exists, and the result is an empty string.

The input constraints are important. The length of num can be up to 100,000 digits, so any algorithm that inspects all possible substrings explicitly would be too slow. Each substring could be up to n digits, and the number of substrings is O(n²), which is infeasible.

Edge cases include strings with all even digits, strings with a single odd digit, strings with the odd number at the start or end, and very large strings up to the maximum length.

Approaches

The brute-force approach would be to generate all possible substrings, check if each one represents an odd number, and keep track of the largest. This works correctly because we check every candidate, but it is too slow: for a string of length n, there are O(n²) substrings, and each substring comparison is O(n), giving O(n³) time complexity. This is not feasible for n up to 10⁵.

The optimal approach leverages the observation that a number is odd if and only if its last digit is odd. To find the largest odd number substring from num, we can simply truncate digits from the right until the last digit becomes odd. This works because removing trailing digits only reduces the number's value, and we want the largest possible substring. Essentially, the answer is the longest prefix of num that ends with an odd digit.

Approach Time Complexity Space Complexity Notes
Brute Force O(n³) O(1) Generate all substrings and check if odd
Optimal O(n) O(1) Scan from the end to find the last odd digit, return prefix

Algorithm Walkthrough

  1. Start from the last character of the string num. The goal is to find the rightmost odd digit.
  2. Iterate backward over num. For each character, check if it is an odd digit ('1', '3', '5', '7', '9').
  3. As soon as we encounter an odd digit, record its index. This index represents the end of the largest odd number substring.
  4. Return the substring from the start of num up to and including this index. If no odd digit is found, return an empty string.
  5. Since we only scan once from the end, this algorithm runs in O(n) time and uses O(1) additional space.

Why it works: The largest odd number must end at the last odd digit of the number, because any suffix of even digits cannot increase the value. Truncating trailing even digits ensures we get the maximum value while satisfying the odd condition.

Python Solution

class Solution:
    def largestOddNumber(self, num: str) -> str:
        # Scan from the end to find the last odd digit
        for i in range(len(num) - 1, -1, -1):
            if num[i] in '13579':
                return num[:i+1]  # Return prefix including this odd digit
        return ""  # No odd digit found

The implementation follows the algorithm exactly. We iterate backward over num, checking each character for oddness. Once found, we return the substring from the start to that position. If no odd digit exists, the function returns an empty string.

Go Solution

func largestOddNumber(num string) string {
    for i := len(num) - 1; i >= 0; i-- {
        if num[i] == '1' || num[i] == '3' || num[i] == '5' || num[i] == '7' || num[i] == '9' {
            return num[:i+1]
        }
    }
    return ""
}

In Go, we use a similar approach. The loop iterates from the end of the string to the start, checking each byte against the set of odd digits. The substring slicing num[:i+1] produces the largest odd number. There are no concerns about integer overflow because we operate on strings, not numeric types.

Worked Examples

Example 1: num = "52"

Step i num[i] Action Result
1 1 '2' Even, continue -
2 0 '5' Odd, return num[:1] "5"

Example 2: num = "4206"

Step i num[i] Action
1 3 '6' Even, continue
2 2 '0' Even, continue
3 1 '2' Even, continue
4 0 '4' Even, continue

Example 3: num = "35427"

Step i num[i] Action
1 4 '7' Odd, return num[:5]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single backward scan through the string of length n
Space O(1) Only a few variables used, no extra data structures

The time complexity is linear because we only inspect each character once. Space is constant because no additional memory is allocated besides the output string slice.

Test Cases

# Provided examples
assert Solution().largestOddNumber("52") == "5"  # Example 1
assert Solution().largestOddNumber("4206") == ""  # Example 2
assert Solution().largestOddNumber("35427") == "35427"  # Example 3

# Single character, odd
assert Solution().largestOddNumber("7") == "7"

# Single character, even
assert Solution().largestOddNumber("8") == ""

# Odd number at the end
assert Solution().largestOddNumber("24689") == "24689"

# Odd number in the middle
assert Solution().largestOddNumber("24687") == "24687"

# All even digits
assert Solution().largestOddNumber("222222") == ""

# Large input with last digit odd
assert Solution().largestOddNumber("2"*100000 + "3") == "2"*100000 + "3"

# Large input with no odd digits
assert Solution().largestOddNumber("2"*100000) == ""
Test Why
"52" Only one odd substring exists
"4206" No odd digits, should return empty
"35427" Entire number is odd
"7" Single-character odd
"8" Single-character even
"24689" Odd at the end, entire string valid
"24687" Odd in the middle, truncation not needed
"222222" All even digits edge case
Large input with last digit odd Stress test for maximum length
Large input all even Stress test returning empty

Edge Cases

All digits are even: For input like "4206" or "222222", there is no odd number, so the function correctly returns an empty string by scanning all digits without finding an odd.

Single-character strings: A string with length one must be handled correctly. "7" returns "7", "8" returns "". The implementation naturally handles this without special cases because the loop still iterates properly.

Large input strings: With inputs up to 10⁵ digits, efficiency is crucial. The linear scan ensures the solution completes quickly, even if the string contains 100,000 characters, whether all even or ending with an odd digit. The algorithm avoids substring generation and numeric conversions, which could be costly.