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.
Related Topics:
Math, String, Greedy
Similar Questions:
Hints:
- In what order should you iterate through the digits?
- If an odd number exists, where must the number start from?
// OJ: https://leetcode.com/problems/largest-odd-number-in-string/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
string largestOddNumber(string s) {
while (s.size() && (s.back() - '0') % 2 == 0) s.pop_back();
return s;
}
};