1903. Largest Odd Number in String
Description
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.
A 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.
Solutions
Solution 1: Reverse Traversal
We can traverse the string from the end to the beginning, find the first odd number, and then return the substring from the beginning to this odd number. If there is no odd number, return an empty string.
The time complexity is $O(n)$, where $n$ is the length of the string $num$. Ignoring the space consumption of the answer string, the space complexity is $O(1)$.
1 2 3 4 5 6 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 |
|
1 2 3 4 5 6 7 8 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|