Problem Description

You are given a string num that represents a large integer. Your task is to find the largest-valued odd integer that can be formed from a substring of num.

A substring is a contiguous sequence of characters within the string. For example, if num = "52", the possible substrings are "5", "52", and "2".

An odd integer is one that ends with an odd digit (1, 3, 5, 7, or 9).

The key insight is that for a number to be odd, it must end with an odd digit. To find the largest odd number that is a substring of num, we need to find a substring that:

1. Ends with an odd digit
2. Is as large as possible (which means including as many leading digits as possible)

Since we want the largest value, and the string represents the integer from left to right with the most significant digits first, we should include as many digits from the left as possible. This means we need to find the rightmost odd digit in the string and return the substring from the beginning up to and including that odd digit.

For example:

• If num = "52", the rightmost odd digit is '5' at index 0, so we return "5"
• If num = "4206", there are no odd digits, so we return ""
• If num = "35427", the rightmost odd digit is '7' at index 4, so we return "35427"

The solution traverses the string from right to left, finds the first odd digit encountered, and returns the substring from the start to that position. If no odd digit is found, it returns an empty string.

Intuition

The first observation is that a number is odd if and only if its last digit is odd. This is a fundamental property of odd numbers - they always end in 1, 3, 5, 7, or 9.

Now, when we want the largest odd substring, we need to think about what makes one number larger than another. In decimal representation, a number with more digits is generally larger (e.g., 523 > 99). If two numbers have the same number of digits, the one with larger leftmost digits is larger.

Since the original string num already represents a number with its digits arranged from most significant to least significant (left to right), any substring that starts from index 0 and includes more digits will be larger than one that includes fewer digits. For example, in "52348", the substring "523" is larger than "52".

This leads us to a key insight: to maximize the value of our odd substring, we should start from the beginning of the string and include as many digits as possible. The only constraint is that our substring must end with an odd digit.

Therefore, our strategy becomes:

1. Find the position of the rightmost odd digit in the string
2. Take the substring from the beginning up to and including that odd digit

Why search from right to left? Because we want to include as many digits as possible. The rightmost odd digit gives us the longest possible substring that ends with an odd digit, which will be the largest odd number we can form.

For example, in "52348", if we search from right to left:

• '8' at index 4 is even, skip
• '4' at index 3 is even, skip
• '3' at index 2 is odd, stop!
• Return num[0:3] which is "523"

This approach guarantees we get the largest possible odd substring in just one pass through the string.

Learn more about Greedy and Math patterns.

Solution Approach

The implementation uses a reverse traversal approach to find the rightmost odd digit in the string.

Here's the step-by-step breakdown of the algorithm:

1. Iterate from right to left: We start from the last character of the string (len(num) - 1) and move towards the beginning (index 0). This is done using a for loop with a step of -1:

   for i in range(len(num) - 1, -1, -1):

2. Check if the current digit is odd: For each character at position i, we convert it to an integer and check if it's odd. The solution uses bitwise AND operation to check for odd numbers:

   if (int(num[i]) & 1) == 1:

   The bitwise AND with 1 (& 1) checks the least significant bit. If it's 1, the number is odd; if it's 0, the number is even. This is equivalent to checking int(num[i]) % 2 == 1.

3. Return the substring: As soon as we find an odd digit at position i, we return the substring from the beginning up to and including position i:

   return num[: i + 1]

   The slice notation num[: i + 1] gives us all characters from index 0 to index i (inclusive).

4. Handle the case with no odd digits: If the loop completes without finding any odd digit, we return an empty string:

   return ''

Time Complexity: O(n) where n is the length of the string. In the worst case, we traverse the entire string once.

Space Complexity: O(1) as we only use a constant amount of extra space for the loop variable. The returned substring doesn't count as extra space since it's part of the output.

The beauty of this solution lies in its simplicity - by traversing from right to left and stopping at the first odd digit we encounter, we automatically get the longest (and therefore largest) substring that ends with an odd digit.

Example Walkthrough

Let's walk through the solution with the example num = "52348".

Step 1: Start from the rightmost character and move left

• Index 4: num[4] = '8' → 8 & 1 = 0 (even), continue
• Index 3: num[3] = '4' → 4 & 1 = 0 (even), continue
• Index 2: num[2] = '3' → 3 & 1 = 1 (odd), found it!

Step 2: Return the substring from start to this position

• Return num[:2+1] = num[:3] = "523"

The answer is "523", which is the largest odd number we can form as a substring.

Let's verify why this is correct:

• All possible odd substrings: "5", "523", "3"
• Among these, "523" has the most digits and therefore is the largest

Now let's trace through another example where num = "4206":

Step 1: Start from the rightmost character

• Index 3: num[3] = '6' → 6 & 1 = 0 (even), continue
• Index 2: num[2] = '0' → 0 & 1 = 0 (even), continue
• Index 1: num[1] = '2' → 2 & 1 = 0 (even), continue
• Index 0: num[0] = '4' → 4 & 1 = 0 (even), continue

Step 2: Loop completes without finding any odd digit

• Return "" (empty string)

This makes sense because there are no odd digits in "4206", so no odd substring can be formed.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the string num. The algorithm iterates through the string from right to left in the worst case (when there are no odd digits or the only odd digit is at the beginning), examining each character once to check if it's odd using the bitwise AND operation (int(num[i]) & 1) == 1, which is an O(1) operation.

Space Complexity: O(1) excluding the space required for the output string. The algorithm only uses a constant amount of extra space for the loop variable i and temporary variables for the digit checking operation. The string slicing operation num[: i + 1] creates a new string for the return value, but this is considered part of the output and not counted towards auxiliary space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding the Problem - Finding Maximum Odd Digit Instead of Maximum Odd Substring

A common mistake is thinking we need to find the largest odd digit in the string and return just that digit, rather than finding the largest odd number that can be formed as a substring.

Incorrect approach:

def largestOddNumber(self, num: str) -> str:
    max_odd = -1
    for digit in num:
        if int(digit) % 2 == 1:
            max_odd = max(max_odd, int(digit))
    return str(max_odd) if max_odd != -1 else ""

This would return "7" for input "35427" instead of the correct answer "35427".

Solution: Remember that we want the largest-valued odd integer, which means including as many leading digits as possible. The correct approach finds the rightmost odd digit and includes everything from the start up to that position.

2. Starting from the Wrong Direction

Another pitfall is traversing from left to right and returning the first odd digit found:

Incorrect approach:

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

For input "52", this would incorrectly return "5" (which happens to be correct), but for "2468135", it would return "24681" instead of "2468135".

Solution: Always traverse from right to left to find the rightmost odd digit, ensuring you get the longest possible substring.

3. Off-by-One Error in Substring Slicing

When finding the odd digit at index i, a common mistake is using incorrect slice notation:

Incorrect approaches:

# Missing the odd digit itself
return num[:i]  # Should be num[:i + 1]

# Including extra character
return num[:i + 2]  # Should be num[:i + 1]

Solution: Use num[:i + 1] to include all characters from index 0 up to and including index i.

4. Inefficient String Concatenation

Some might try to build the result character by character from right to left:

Inefficient approach:

def largestOddNumber(self, num: str) -> str:
    result = ""
    found_odd = False
    for i in range(len(num) - 1, -1, -1):
        result = num[i] + result
        if int(num[i]) % 2 == 1:
            found_odd = True
            break
    return result if found_odd else ""

This unnecessarily builds the string character by character when a simple slice would suffice.

Solution: Use Python's efficient string slicing num[:i + 1] to get the substring in one operation.