Largest Odd Number in String

Difficulty: Easy | Acceptance: 67.40% | Paid: No Topics: Math, String, Greedy

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.

An integer is odd if it ends in 1, 3, 5, 7, or 9.

• Examples
• Constraints
• Greedy: Rightmost Odd Digit
• Brute Force: Check All Substrings
• Iterative: Track Last Odd

Examples

Input: num = "52"
Output: "5"
Explanation: The only non-empty substrings are "5", "2", and "52". "5" is the only odd number.

Input: num = "4206"
Output: ""
Explanation: There are no odd digits in the string, so no odd substring exists.

Input: num = "35427"
Output: "35427"
Explanation: "35427" is already an odd number.

Constraints

1 <= num.length <= 10⁵
num consists of only digits and does not contain any leading zeros.

Greedy: Rightmost Odd Digit

Intuition A number is odd if and only if its last digit is odd. To maximize the value of the odd number, we want the longest possible substring starting from the beginning. Therefore, we simply need to find the rightmost odd digit in the string and return the substring from the start up to that digit.

Steps

• Iterate through the string from the end towards the beginning.
• Check if the current digit is odd (1, 3, 5, 7, 9).
• If an odd digit is found at index i, return the substring num[0...i].
• If the loop finishes without finding an odd digit, return an empty string.

class Solution:
    def largestOddNumber(self, num: str) -> str:
        for i in range(len(num) - 1, -1, -1):
            if int(num[i]) % 2 != 0:
                return num[:i + 1]
        return ""

Complexity

• Time: O(n), where n is the length of the string. In the worst case, we traverse the whole string.
• Space: O(1) auxiliary space, though creating the substring takes O(n) space for the output.
• Notes: This is the optimal approach as it requires a single pass from the end.

Brute Force: Check All Substrings

Intuition We can generate every possible substring of num, check if it represents an odd integer, and keep track of the largest one found so far.

Steps

• Initialize result as an empty string.
• Use two nested loops to generate all substrings. The outer loop i goes from 0 to n-1 (start index), and the inner loop j goes from i to n-1 (end index).
• Extract the substring num[i...j].
• Check if the last character of the substring is an odd digit.
• If it is odd, compare its length with result. If it is longer, or same length but lexicographically larger, update result.
• Return result.

class Solution:
    def largestOddNumber(self, num: str) -> str:
        res = ""
        n = len(num)
        for i in range(n):
            for j in range(i, n):
                sub = num[i:j+1]
                if int(sub[-1]) % 2 != 0:
                    if len(sub) > len(res) or (len(sub) == len(res) and sub > res):
                        res = sub
        return res

Complexity

• Time: O(n²), where n is the length of the string. Generating all substrings takes quadratic time.
• Space: O(1) auxiliary space.
• Notes: This approach is inefficient for large inputs (n up to 10⁵) and will result in Time Limit Exceeded (TLE).

Iterative: Track Last Odd

Intuition Instead of iterating from the end, we can iterate from the start to the end. We keep track of the index of the last odd digit we have seen. The largest odd number must end at the last odd digit present in the string.

Steps

• Initialize lastOddIndex to -1.
• Iterate through the string from index 0 to n-1.
• If the current digit is odd, update lastOddIndex to the current index i.
• After the loop, if lastOddIndex is not -1, return the substring from 0 to lastOddIndex + 1.
• Otherwise, return an empty string.

class Solution:
    def largestOddNumber(self, num: str) -> str:
        last_odd = -1
        for i, ch in enumerate(num):
            if int(ch) % 2 != 0:
                last_odd = i
        return num[:last_odd + 1] if last_odd != -1 else ""

Complexity

• Time: O(n), where n is the length of the string. We traverse the string once.
• Space: O(1) auxiliary space.
• Notes: This is functionally equivalent to the greedy approach but iterates forward. It is also optimal.