Largest Odd Number in String | Leetcode 1903 | Step-by-Step Solution Explained

The Largest Odd Number in String problem asks us to find the largest-valued odd integer that can be formed from a given numeric string.

• We are given a numeric string num.
• We must return the largest odd number that can be formed by removing some trailing digits (from the right side) of the string.
• If no odd number can be formed, return an empty string.

Here’s the [Problem Link] to begin with.

Example 1

Input: num = "52"
Output: "5"
Explanation: "52" → remove last digit "2" → largest odd number is "5".

Example 2

Input: num = "4206"
Output: ""
Explanation: No odd digit exists, so return "".

Example 3

Input: num = "35427"
Output: "35427"
Explanation: The whole number is already odd, so return the entire string.

Intuition and Approach

To solve the Largest Odd Number in String problem, let’s carefully analyze:

1. Odd number rule:
   • A number is odd if its last digit is odd.
   • Digits 1, 3, 5, 7, 9 are odd.
   • Digits 0, 2, 4, 6, 8 are even.
2. Observation:
   • Since we can only remove digits from the end of the string, the largest odd number must be a prefix of the original string ending at the last odd digit.
3. Greedy solution:
   • Traverse the string from right to left.
   • Find the first digit that is odd.
   • Return the substring from the start up to that digit.
   • If no odd digit exists, return an empty string.

This greedy approach works because the leftmost part of the string always keeps the number as large as possible, and the last odd digit ensures the number is odd.

Code Implementation

Here’s the Python code using the greedy approach:

class Solution:
    def largestOddNumber(self, num: str) -> str:
        n = len(num)
        # Traverse from right to left
        for i in range(n - 1, -1, -1):
            if int(num[i]) % 2 == 1:  # Check if digit is odd
                return num[: i + 1]   # Return prefix ending at last odd digit
        return ""  # No odd digit found

Code Explanation

• Start scanning the string from the last digit.
• If the digit is odd (num[i] % 2 == 1), we cut the string at that position.
• The substring num[:i+1] is the largest odd number possible.
• If we reach the beginning and find no odd digits, return "".

This avoids unnecessary computations and ensures optimal performance.

Dry Run Example

Input: "42056"

• Start from rightmost digit: 6 (even). Skip.
• Next digit: 5 (odd). Found!
• Return substring "4205".

Output: "4205"

Time and Space Complexity

• Time Complexity:
  • We scan the string once, so complexity is O(N), where N is the length of the string.
• Space Complexity:
  • We only use a few variables, so complexity is O(1).

Why this is Optimal

This greedy solution is optimal because:

• We only care about the last odd digit.
• Once we find it, we don’t need to check further.
• Cutting at that position guarantees the largest possible odd number.

Conclusion

The Largest Odd Number in String problem teaches us the power of greedy algorithms and the importance of simple observations in problem solving.

• Traverse the string from right to left.
• Stop at the last odd digit.
• Return the substring ending at that digit.

This runs in O(N) time and is space-efficient.

This approach is interview-friendly and LeetCode-optimized, and understanding it helps strengthen string manipulation and greedy problem-solving skills.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.