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

substring is a contiguous sequence of characters within a string.

Example 1:

Input: num = "52"
Output: "5"
Explanation: The only non-empty substrings are "5", "2", and "52". "5" is the only odd number.


Example 2:

Input: num = "4206"
Output: ""
Explanation: There are no odd numbers in "4206".


Example 3:

Input: num = "35427"
Output: "35427"
Explanation: "35427" is already an odd number.


Constraints:

• 1 <= num.length <= 105
• num only consists of digits and does not contain any leading zeros.

## Solution: Find right most odd digit

We just need to find the right most digit that is odd, answer will be num[0:r].

Proof:
Assume the largest number is num[i:r] i > 0, we can always extend to the left, e.g. num[i-1:r] which is also an odd number and it’s larger than num[i:r] which contradicts our assumption. Thus the largest odd number (if exists) must start with num[0].

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

## C++

If you like my articles / videos, donations are welcome.

Buy anything from Amazon to support our website

Paypal
Venmo
huahualeetcode