Problem

Solution

Intuition

This problem requires us to find the largest odd number from a string that does not contain any leading zeros. Not containing leading zeros is actually very helpful as the largest possible odd number will start at the first number and go until the rightmost odd number in the string. Knowing this, we can iterate backwards from the right in the string and once we find the first odd number from the right, return the string from the first number until the first odd number from the right.

For example, if we have 1664388, we iterate backwards until we find the 3, and then return the entire string to that point, i.e.: 16643 as the largest odd number will have the most possible digits.

Approach

1. Iterate from the right until the rightmost odd number is found
2. Return from the beginning of the string until the rightmost odd number.
3. Return an empty string if only even numbers are found.

Complexity

• Time complexity: $O(n)$. We iterate through the entire string once.
• Space complexity: $O(1)$. We don’t utilize any significant space for the solution.

Code

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