{x}
blog image

Largest Odd Number in String

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

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

 

Example 1:

Input: num = "52"
Output: "5"
Explanation: The only non-empty substrings are "5", "2", and "52". "5" is the only odd number.

Example 2:

Input: num = "4206"
Output: ""
Explanation: There are no odd numbers in "4206".

Example 3:

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

 

Constraints:

  • 1 <= num.length <= 105
  • num only consists of digits and does not contain any leading zeros.

Solution Explanation for Largest Odd Number in String

This problem asks to find the largest odd number that is a substring of a given input string num. The solution involves efficiently iterating through the string to identify the longest substring ending in an odd digit.

Approach: Reverse Traversal

The most efficient approach is to traverse the input string num from right to left (least significant digit to most significant). This allows us to find the rightmost odd digit quickly. Once an odd digit is found, the substring from the beginning of the string up to (and including) that digit represents the largest odd number. If no odd digit is found, the result is an empty string.

Time and Space Complexity Analysis

  • Time Complexity: O(n), where n is the length of the input string num. We iterate through the string at most once.

  • Space Complexity: O(1). We are using a constant amount of extra space, regardless of the input size. The space used to store the result substring is not considered in space complexity analysis within this context as the size of the output is bounded by the input.

Code Implementation in Multiple Languages

The following code demonstrates the solution in several programming languages:

Python:

class Solution:
    def largestOddNumber(self, num: str) -> str:
        for i in range(len(num) - 1, -1, -1):
            if int(num[i]) % 2 != 0: # Check for odd digit
                return num[:i + 1]  #Return substring up to the odd digit
        return ''  # Return empty string if no odd digit is found

Java:

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

C++:

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

Go:

func largestOddNumber(num string) string {
    for i := len(num) - 1; i >= 0; i-- {
        digit := int(num[i] - '0')
        if digit%2 != 0 {
            return num[:i+1]
        }
    }
    return ""
}

Javascript:

var largestOddNumber = function(num) {
    for (let i = num.length - 1; i >= 0; i--) {
        if (parseInt(num[i]) % 2 != 0) {
            return num.substring(0, i + 1);
        }
    }
    return "";
};

Typescript:

function largestOddNumber(num: string): string {
    for (let i = num.length - 1; i >= 0; i--) {
        if (parseInt(num[i]) % 2 !== 0) {
            return num.substring(0, i + 1);
        }
    }
    return "";
}

All these code snippets follow the same logic: iterating from right to left, checking for an odd digit, and returning the appropriate substring. The minor differences reflect the syntactic variations between the languages.