1903. Largest Odd Number in String

Intuition

To find the largest-valued odd integer substring, we don't need to check every possible substring. Since the original string represents a number and all digits are ordered from most significant to least significant (like a real number), the largest odd-valued substring will simply be the longest prefix (from the start) ending at the rightmost odd digit.

If we find the last odd digit in the string while iterating from the end, the substring from the start to that index will be our answer.

Complexity

Space Complexity	Time Complexity
$\text{O}(1)$	$\text{O}(n)$

Code

public String largestOddNumber(String numberStr) {
    // Traverse from end to start
    for (int index = numberStr.length() - 1; index >= 0; --index) {
        // Convert character to integer and check if it's odd
        if ((numberStr.charAt(index) - '0') % 2 != 0) {
            // Return the substring from start to current index (inclusive)
            return numberStr.substring(0, index + 1);
        }
    }

    // No odd digit found, return empty string
    return "";
}