Explorer
Data Structures & Algorithms

Find the largest odd number that is a substring of a string of digits.

Problem Statement

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

Examples

Input: num = "52"

Output: "5"

Explanation: "5" is the largest odd substring in "52".

Input: num = "4206"

Output: ""

Explanation: No odd digit exists in "4206", so the output is an empty string.

Input: num = "35427"

Output: "35427"

Explanation: "35427" is the largest odd substring in "35427".

Complexity

Time Complexity: O(N)

Space Complexity: O(1)

Hints

šŸ’” Hint 1: An integer is odd if and only if its last digit is odd. šŸ’” Hint 2: The largest prefix that ends with an odd digit will be the largest odd substring. šŸ’” Hint 3: Traverse backwards from the end of the string. The first odd digit found gives the substring from 0 to i.

Editorial & Approach

Problem Overview & Intuition

Any substring starting at index 0 and ending at index i represents a valid prefix. Since larger values correspond to longer prefixes, the largest odd number is simply the prefix ending at the rightmost odd digit.

Step-by-Step Approach

  1. Iterate i backwards from num.length - 1 down to 0.
  2. Check if parseInt(num[i]) % 2 !== 0.
  3. If odd, return num.substring(0, i + 1).
  4. If no odd digit is found, return "".

Optimal Implementation (JavaScript)

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

Complexity Analysis

Time Complexity O(N) ā€” single backwards pass.
Space Complexity O(1) auxiliary space (excluding returned substring).

Edge Cases & Corner Traps Handled

  • No odd digits: "4206" -> "".
  • Last digit is odd: entire string returned.
  • Only first digit is odd: "52" -> "5".

Largest Odd Number in a String

Easy
You are given a string `num`, representing a large integer. Return the largest-valued odd integer (as a substring) that is a non-empty substring of `num`, or an empty string `""` if no odd number exists. A substring is a contiguous sequence of characters within a string.
Example Scenarios
1Example 1
Input: num = "52"
Output: "5"
Explanation:

"5" is the largest odd substring in "52".

2Example 2
Input: num = "4206"
Output: ""
Explanation:

No odd digit exists in "4206", so the output is an empty string.

3Example 3
Input: num = "35427"
Output: "35427"
Explanation:

"35427" is the largest odd substring in "35427".

Editor
Loading Editor...
num =
"52"
Output:Click "Run" above to execute and verify your code here.
5