We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Largest Odd Number in String

Difficulty: Easy

Problem Description

You are given a string num, representing a large integer. Return the largest-valued odd integer (as a string) that is a non-empty substring of num, or an empty string "" if no odd integer exists. A substring is a contiguous sequence of characters within a string.

Key Insights

  • An odd number is defined by its last digit being odd (1, 3, 5, 7, or 9).
  • The largest odd substring can be found by checking the string from the end, as longer substrings may not be necessary if we find a valid odd number early.
  • If no odd digits exist in the string, the result should be an empty string.

Space and Time Complexity

Time Complexity: O(n) - where n is the length of the string. Space Complexity: O(1) - only a few variables are used for storage.

Solution

To solve the problem, we can iterate through the string from the end to the beginning. We check each character to see if it is an odd digit. If we find an odd digit, we can return the substring from the start of the string to that index (inclusive). This guarantees that we are returning the largest odd number possible as a substring. If we finish checking the string and find no odd digits, we return an empty string.

Code Solutions

def largestOddNumber(num: str) -> str:
    # Iterate from the end of the string to find the last odd digit
    for i in range(len(num) - 1, -1, -1):
        if int(num[i]) % 2 == 1:  # Check if the digit is odd
            return num[:i + 1]  # Return the substring up to and including this digit
    return ""  # Return empty string if no odd digit found
← Back to All Questions