Press "Enter" to skip to content

花花酱 LeetCode 1903. Largest Odd Number in String

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.


  • 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].

Answer must start with num[0].
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)


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

Buy anything from Amazon to support our website


Be First to Comment

Leave a Reply