Largest Odd Number in String

How it works

The largest odd substring must start from the beginning of the string (to maximize length and leading digits) and end at the rightmost odd digit. Why? Because starting from index 0 gives us the largest possible prefix, and we just need to find where to cut it off to make it odd.

By scanning from right to left, we find the first (rightmost) odd digit and return the prefix up to and including that position.

Steps

1. Traverse the string from the last character to the first.
2. At each position, check if the digit is odd (using modulo 2).
3. When an odd digit is found, return the substring from the beginning up to and including this position.
4. If no odd digit is found, return an empty string.

Complexity

• Time complexity: O(n)
• Space complexity:
  • O(1) extra space.
  • O(n) for the output string.

Things to watch for

Starting the Search from the Wrong End

To find the largest odd number, you must keep the prefix as long as possible and only trim even digits from the end. Searching from the left or trying to find substrings that don't start at index 0 will miss the optimal answer. The largest odd substring always starts at the beginning of the string and extends to the rightmost odd digit.

Incorrectly Checking for Odd Digits

A digit is odd if it is 1, 3, 5, 7, or 9. A common mistake is checking the wrong character or using incorrect modulo logic. Remember that num[i] is a character, so you need to convert it to its numeric value (e.g., num[i] - '0') before checking if it's odd with % 2 == 1 or & 1.

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

class Solution {
public:
    string largestOddNumber(string num) {
        for (int i = num.size() - 1; i >= 0; i--) {
            if ((num[i] - '0') % 2 == 1) {
                return num.substr(0, i + 1);
            }
        }
        return "";
    }
};