Solution: Largest Odd Number in String

Statement

You are given a string, num, which represents a large integer. Your task is to find the largest odd-valued integer that can be formed as a non-empty substring of num. Return this odd integer as a string. If no odd integer exists, return an empty string ("").

Note: A substring is a continuous sequence of characters within a string.

Constraints:

• $1 \leq$num.length $\leq 10^4$

• num only consists of digits and does not contain any leading zeros.

Solution

This problem aims to find the largest odd-valued integer that can be formed as a contiguous substring of the input string num. As odd numbers are determined by their last digit $(1,3,5,7, or \ 9)$, the largest odd-valued substring can only occur up to the last odd digit in the string. We will use a greedy approach to solve this by scanning the string from the end. We can immediately determine the largest valid odd substring once we encounter the rightmost odd digit.

Now, let’s look at the solution steps:

• Start with the input string num, representing a large integer.

• Traverse the string from the last character to the first.

• For each character, check if it is an odd digit (1, 3, 5, 7, 9).

• If an odd digit is found:

  • Extract the substring from the start of the string up to including this odd digit.

  • Return the extracted substring.

• Return an empty string if no odd digit is found after traversing the entire string "".

Let’s look at the following illustration to get a better understanding of the solution: