Largest Odd Number in String
Largest odd-valued substring of a digit string — scan from the right for the first odd digit.
2 min read
greedy string
Problem#
Return the largest odd-valued substring of num, or "" if none exists.
Examples#
"52"→"5""4206"→"""35427"→"35427"
Constraints#
1 <= num.length <= 10^5.
Approach#
Scan from right; first odd digit found is the suffix-end of the answer. Return num.substr(0, lastOddIndex + 1).
Solution#
class Solution {public: string largestOddNumber(string num) { for (int i = num.size() - 1; i >= 0; --i) { if ((num[i] - '0') % 2 == 1) return num.substr(0, i + 1); } return ""; }};func largestOddNumber(num string) string { for i := len(num) - 1; i >= 0; i-- { if (num[i]-'0')%2 == 1 { return num[:i+1] } } return ""}class Solution: def largestOddNumber(self, num: str) -> str: for i in range(len(num) - 1, -1, -1): if int(num[i]) % 2 == 1: return num[:i + 1] return ""function largestOddNumber(num) { for (let i = num.length - 1; i >= 0; i--) { if ((num.charCodeAt(i) - 48) % 2 === 1) return num.slice(0, i + 1); } return "";}class Solution { public String largestOddNumber(String num) { for (int i = num.length() - 1; i >= 0; i--) { if ((num.charAt(i) - '0') % 2 == 1) return num.substring(0, i + 1); } return ""; }}function largestOddNumber(num: string): string { for (let i = num.length - 1; i >= 0; i--) { if ((num.charCodeAt(i) - 48) % 2 === 1) return num.slice(0, i + 1); } return "";}Editorial#
A number is odd iff its last digit is odd. The largest-magnitude odd substring keeps as many leading digits as possible — so we want the rightmost odd digit, and everything before it.
Complexity#
- Time: O(n).
- Space: O(1).
Concept revision#
Related#