Given a numeric string, return the longest prefix that forms an odd number.
Problem
You are given a string num consisting only of digits. Your task is to return the largest-valued odd number that can be formed by taking a prefix of num.
A prefix is a substring that starts at the first character of the string. The returned number must be non-empty and its last digit must be odd.
If no such prefix exists, return an empty string.
Intuition
Since the number is represented as a string and all prefixes preserve the original order, the largest odd prefix is simply the longest prefix whose last digit is odd.
Input Format
- A single string
numcontaining only characters'0'through'9'. numrepresents a non-negative integer with no sign.
Output Format
- Return the longest prefix of
numthat ends in an odd digit. - If no prefix ends in an odd digit, return
"".
Constraints
1 <= num.length <= $10^{5}$numcontains only digits0-9.- The answer, if it exists, is a prefix of
num.
Example 1
Input
num = "52"
Output
"5"
Explanation
The prefixes are "5" and "52". Only "5" is odd, so it is the largest odd-number prefix.
Example 2
Input
num = "4206"
Output
""
Explanation
No prefix ends with an odd digit, so the answer is empty.
Show 1 more example
Example 3
Input
num = "35427"
Output
"35427"
Explanation
The entire string ends in 7, which is odd, so the whole string is the largest odd prefix.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.