1903. Largest Odd Number in String

 

Intuition

The goal is to find the largest odd number that can be formed by removing some digits from the right end of the given string num. The key insight is that the largest odd number will be the longest prefix of num that ends with an odd digit. If the last digit is odd, the entire number is the answer. Otherwise, we need to find the rightmost odd digit and return the substring up to that digit.

Approach

Check the Last Digit:
Start by checking if the last digit of num is odd. If it is, return num as it is already the largest odd number.
Iterate from the End:
If the last digit is even, iterate from the second last digit to the first digit.
For each digit, check if it is odd.
If an odd digit is found, return the substring of num from the start to this digit (inclusive).
Return Empty String:
If no odd digit is found in the entire string, return an empty string.

Complexity

• Time complexity: (O(n)), where (n) is the length of the string num. This is because we may need to check each digit once.

• Space complexity: (O(1)), as we are using a constant amount of extra space regardless of the input size.

Code

JavaScript

/**
 * @param {string} num
 * @return {string}
 */
var largestOddNumber = function(num) {
    if(parseInt(num.charAt(num.length - 1)) % 2 != 0){
        return num;
    }
    for (let i = 2; i <= num.length; i++) {
        if(parseInt(num.charAt(num.length - i)) % 2 != 0){
            return num.slice(0, num.length - i + 1);
        }
    }
    return "";
};