Largest odd number in string

Problem Link

1903. Largest Odd Number in String – LeetCode

Problem Statement

You are given a string num representing a large integer.
Return the largest-valued odd integer (as a non-empty substring) of num, or return "" if no odd integer exists.

A substring is a contiguous sequence of characters within the string.

Examples

Example 1:

Input: num = "52"
Output: "5"
Explanation: The substrings are "5", "2", and "52". Only "5" is odd.

Example 2:

Input: num = "4206"
Output: ""
Explanation: No odd digits exist.

Example 3:

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

Constraints

• 1 <= num.length <= 10⁵

• num only consists of digits

• No leading zeros

Intuition

We're trying to find the rightmost odd digit in the string.
Once we find it, the largest odd number will be the prefix substring from the start of the string up to that index.

Why?

• Any digit after the last odd digit would make the number even.

• Including all digits up to the last odd digit gives the maximum possible odd number as a substring.

Approach

1. Traverse the string from end to start.

2. For each character, check if it's odd.

3. As soon as an odd digit is found at index i, return num.substring(0, i + 1).

4. If no odd digit is found, return "".

Java Code (Optimized Version)

class Solution {
    public String largestOddNumber(String num) {
        for (int i = num.length() - 1; i >= 0; i--) {
            char ch = num.charAt(i);
            if ((ch - '0') % 2 == 1) {
                return num.substring(0, i + 1);
            }
        }
        return "";
    }
}

Java Code

class Solution {
    public String largestOddNumber(String num) {
        StringBuilder sb = new StringBuilder();
        int inc = 0;
        for (int i = num.length() - 1; i >= 0; i--) {
            char ch = num.charAt(i);
            if (isOdd(ch) && inc == 0) {
                sb.insert(0, ch);
                inc++;
            } else if (inc == 1) {
                sb.insert(0, ch);
            }
        }
        return sb.toString();
    }

    private static boolean isOdd(char ch) {
        return (ch == '1' || ch == '3' || ch == '5' || ch == '7' || ch == '9');
    }
}

✅ Works correctly
🟡 Slightly less optimal due to unnecessary use of StringBuilder and extra state tracking.

Time and Space Complexity

Dry Run

Input: "5200"

• Traverse from right:

  • '0' → even → skip

  • '0' → even → skip

  • '2' → even → skip

  • '5' → odd → return "52".substring(0, 1+1) → "52"

Output: "5"

Conclusion

The key idea is:

Trim from the right until the last character is odd.

This approach is efficient, simple, and uses string manipulation and parity checking.

Use the optimized version unless there's a need to construct substrings manually.