Largest Odd Number in String

easy string greedy

Problem

Given a digit-only string num, return the largest substring that represents an odd number, or "" if none.

Inputnum = "35427"

Output"35427"

Last digit 7 is odd, so the whole string qualifies.

num

def largest_odd_number(num):
    for i in range(len(num) - 1, -1, -1):
        if int(num[i]) % 2 == 1:
            return num[:i + 1]
    return ''

function largestOddNumber(num) {
  for (let i = num.length - 1; i >= 0; i--) {
    if ((num.charCodeAt(i) - 48) % 2 === 1) return num.slice(0, i + 1);
  }
  return '';
}

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

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

Explanation

A number is odd exactly when its last digit is odd. To get the largest odd substring, we want to keep as many leading digits as possible, so we scan from the right end looking for the first odd digit.

The loop runs i from the last index down to 0. As soon as num[i] is odd, the prefix num[:i+1] is the answer — it is the longest possible substring that still ends on an odd digit. If we never find an odd digit, every substring would be even, so we return "".

Why the prefix? Any longer piece would have to include the even digits to the right of i, making the whole thing end in an even digit and therefore even.

Example: num = "35427". The last digit 7 is odd, so the entire string already qualifies and the answer is "35427". For "52", the 2 is even but the 5 is odd, so we return "5".

In the worst case we scan the whole string once, which makes this linear in the number of digits.

Time: O(n) Space: O(1)