[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.

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.

字符串中的最大奇数。

给你一个字符串 num ，表示一个大整数。请你在字符串 num 的所有 非空子字符串 中找出 值最大的奇数 ，并以字符串形式返回。如果不存在奇数，则返回一个空字符串 “” 。
子字符串 是字符串中的一个连续的字符序列。

思路

思路是贪心。因为只允许删除字符，但是从左往右删除字符是无法改变数字的奇偶性的，所以思路是从右往左遍历 input 字符串，看看最右边一个字符串到底是奇数还是偶数。如果是奇数就可以直接返回了；如果是偶数，则删除当前字符，接着看左边的字符。

复杂度

时间O(n)
空间O(1)

代码

Java实现

class Solution {
    public String largestOddNumber(String num) {
        int n = num.length();
        for (int i = n - 1; i >= 0; i--) {
            int d = num.charAt(i) - '0';
            if (d % 2 == 1) {
                String str = num.substring(0, i + 1);
                return str;
            }
        }
        return "";
    }
}