Largest Odd Number in String

Easy
556.

Largest Odd Number in String

Largest Odd Number in String is an easy coding problem on strings, math and greedy, asked in Amazon and Adobe interviews.

You are given a string num of digits. Return the largest-valued odd integer that is a non-empty substring of num, as a string.

If no odd substring exists, return the empty string.

Example 1

Input
num = "52"
Output
5
Explanation
The only odd substring is "5".

Example 2

Input
num = "4206"
Output
Explanation
Every digit is even.

Example 3

Input
num = "35427"
Output
35427
Explanation
The whole string is already odd.

Constraints

  • 1 <= num.length <= 100000
  • num consists of digits only and has no leading zeros.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} num
 * @return {string}
 */
var largestOddNumber = function(num) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Largest Odd Number in String — Problem & Solution

Largest Odd Number in String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Largest Odd Number in String is an easy coding problem on strings, math and greedy, asked in Amazon and Adobe interviews.

  • Difficulty: Easy
  • Topics: Strings, Math, Greedy
  • Asked at: Amazon, Adobe
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given a string num of digits. Return the largest-valued odd integer that is a non-empty substring of num, as a string.

If no odd substring exists, return the empty string.

Example 1

Input: num = "52"
Output: 5
Explanation: The only odd substring is "5".

Example 2

Input: num = "4206"
Output: 
Explanation: Every digit is even.

Example 3

Input: num = "35427"
Output: 35427
Explanation: The whole string is already odd.

Constraints

  • 1 <= num.length <= 100000
  • num consists of digits only and has no leading zeros.

Hints for Largest Odd Number in String

  1. Hint 1

    A number is odd exactly when its last digit is odd.

  2. Hint 2

    To make the value as large as possible, keep the prefix as long as possible.

  3. Hint 3

    So scan from the right for the last odd digit and return everything up to and including it.

How to solve Largest Odd Number in String

Any odd substring must end at an odd digit. Among substrings ending at a fixed position, the longest — the whole prefix — is the largest, and a longer prefix always beats a shorter one for a digit string with no leading zeros.

Approach

  1. Scan num from the last index backwards.
  2. At the first odd digit found at index i, return num[0..i].
  3. Return the empty string if no odd digit exists.

Why it works

Extending a substring leftward can only increase its value (it adds more significant digits), so the best choice ends at the rightmost odd digit and starts at index 0.

Complexity

  • Time — O(n)
  • Space — O(n) for the returned prefix

Pitfalls

  • Searching for the largest odd digit rather than the rightmost one gives a shorter, smaller answer.
  • Enumerating substrings is O(n²) and hopeless at 100,000 characters.
  • The answer keeps any interior zeros — only leading zeros would be a problem, and the input has none.

Reference solution

Python

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

Java

public static 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 "";
}

C++

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 "";
}

JavaScript

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

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Greedy Algorithms