How do I find the largest odd number in a string efficiently?

Scan from the end to find the last odd digit, then return the substring up to that point.

Why is a greedy backward scan the right pattern for this problem?

Because the last odd digit ensures the maximal substring value, preserving all higher digits on the left.

What if the string contains only even digits?

Return an empty string, as no odd substring exists.

Can I iterate from left to right instead?

Left-to-right requires extra logic to track potential maximal odd substrings; right-to-left guarantees the correct result directly.

How does invariant validation apply here?

It ensures that slicing at the last odd digit always produces the largest odd substring without missing higher digits to the left.

#1903

Easy

auto_awesome贪心·invariant

LeetCode 题解工作台

字符串中的最大奇数

给你一个字符串 num ，表示一个大整数。请你在字符串 num 的所有非空子字符串中找出值最大的奇数，并以字符串形式返回。如果不存在奇数，则返回一个空字符串 "" 。子字符串是字符串中的一个连续的字符序列。示例 1：输入： num = "52" 输出： "5" 解释：非空子字符串仅…

数学字符串贪心

题目描述

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

子字符串 是字符串中的一个连续的字符序列。

示例 1：

输入：num = "52"
输出："5"
解释：非空子字符串仅有 "5"、"2" 和 "52" 。"5" 是其中唯一的奇数。

示例 2：

输入：num = "4206"
输出：""
解释：在 "4206" 中不存在奇数。

示例 3：

输入：num = "35427"
输出："35427"
解释："35427" 本身就是一个奇数。

提示：

1 <= num.length <= 10⁵
num 仅由数字组成且不含前导零

lightbulb

解题思路

方法一：逆序遍历

我们可以从后往前遍历字符串，找到第一个奇数，然后返回从开头到该奇数的子字符串即可。如果不存在奇数，则返回空字符串。

时间复杂度 $O(n)$ ，其中 $n$ 是字符串 $num$ 的长度。忽略答案字符串的空间消耗，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

class Solution:
    def largestOddNumber(self, num: str) -> str:
        for i in range(len(num) - 1, -1, -1):
            if (int(num[i]) & 1) == 1:
                return num[: i + 1]
        return ''

speed

复杂度分析

指标	值
时间	O(n)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Asks about scanning from left vs right and why greedy works here
question_mark
Mentions handling extremely long numeric strings efficiently
question_mark
Probes understanding of odd/even digit significance for substring selection

warning

常见陷阱

外企场景

error
Checking every possible substring leads to O(n^2) time complexity, which is unnecessary
error
Returning the first odd digit from the start instead of the last may produce a smaller number
error
Forgetting to return empty string when no odd digit exists

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find the smallest odd substring instead of the largest
arrow_right_alt
Allow non-contiguous digits but still maximize odd value
arrow_right_alt
Handle strings with leading zeros or negative signs

help

常见问题

外企场景

继续练习

#1927 求和游戏 #2038 如果相邻两个颜色均相同则删除当前颜色 #1247 交换字符使得字符串相同