algoadvance

You are given a string num consisting of digits only. Return the largest-valued odd number that is a non-empty substring of num, or an empty string “” if no odd number exists.

Clarifying Questions

  1. Input Constraints: Are there any constraints on the size of the input string?
    • Yes, the length of num will be between 1 and 10^5.
  2. Digits Only: Does the string num contain only numeric characters?
    • Yes, the string consists of digits from ‘0’ to ‘9’ only.
  3. Substring: Does a substring have to be contiguous?
    • Yes, a substring is any contiguous sequence of characters within the string.

Strategy

  1. Identify the Last Odd Digit: The largest possible odd number within the string would end with the last odd digit in the string. This is because appending more digits to the front does not change whether the number is odd or its factorial value, but it can make the number larger.
  2. Extract the Substring: Once the position of the last odd digit is found, the largest odd number will be the substring from the beginning of the string to that position.

Code

Here’s the Python code to solve the problem:

def largestOddNumber(num: str) -> str:
    # Loop from the end of the string to the beginning
    for i in range(len(num) - 1, -1, -1):
        # Check if the character is an odd digit
        if int(num[i]) % 2 != 0:
            # Return the substring from the start to this odd digit
            return num[:i+1]
    # Return an empty string if no odd digit is found
    return ""

# Example usage:
print(largestOddNumber("52")) # Output: "5"
print(largestOddNumber("4206")) # Output: ""
print(largestOddNumber("35427")) # Output: "35427"

Time Complexity

This ensures that the solution is efficient and works within the constraints provided.

Try our interview co-pilot at AlgoAdvance.com