难度: Easy
给你一个字符串 num ，表示一个大整数。请你在字符串 num 的所有 非空子字符串 中找出 值最大的奇数 ，并以字符串形式返回。如果不存在奇数，则返回一个空字符串 "" 。
子字符串 是字符串中的一个连续的字符序列。
示例 1：
输入：num = "52" 输出："5" 解释：非空子字符串仅有 "5"、"2" 和 "52" 。"5" 是其中唯一的奇数。
示例 2：
输入：num = "4206" 输出："" 解释：在 "4206" 中不存在奇数。
示例 3：
输入：num = "35427" 输出："35427" 解释："35427" 本身就是一个奇数。
提示：
1 <= num.length <= 105num 仅由数字组成且不含前导零运行时间: 33 ms
内存: 16.7 MB
class Solution:
def largestOddNumber(self, num: str) -> str:
odd = "13579"
for i in range(len(num)-1, -1, -1):
if num[i] in odd:
return num[:i+1]
return ""
这个题解的核心思路是利用一个逆向遍历来找到字符串中最后一个出现的奇数字符。因为最大的奇数子字符串一定以奇数结尾，所以从字符串的末尾向前查找第一个奇数字符是一个高效的策略。一旦找到这样的字符，整个从字符串开头到这个字符的子字符串就是所求的最大奇数子字符串。如果整个字符串中没有奇数字符，则返回空字符串。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def largestOddNumber(self, num: str) -> str:
odd = '13579' # 奇数字符集
# 从字符串末尾开始向前遍历
for i in range(len(num)-1, -1, -1):
if num[i] in odd: # 如果找到奇数字符
return num[:i+1] # 返回从开头到这个字符的子字符串
return '' # 如果没有奇数，返回空字符串
在这个特定的问题中，我们的目标是找到最大的奇数子字符串，即以奇数结尾的最长子字符串。从后向前遍历可以直接定位到最后一个奇数字符，这样可以立即确定从字符串开始到这个奇数字符的子字符串就是答案。如果从前向后遍历，我们需要记录每一个奇数字符的位置，并在遍历完成后确定哪一个奇数字符后的部分最长，这增加了复杂性和可能的计算量。
是的，这是正确的。因为问题要求的是最大的奇数子字符串，所以必须包括第一个字符直到最后一个奇数字符。这样的子字符串包含了可能的最长长度，且确保以奇数结尾，符合题目的要求。
使用额外的数据结构存储每个奇数的位置虽然可以在某些情况下加速查找，但会增加空间复杂度。对于本题，单次逆向遍历已足够高效（时间复杂度为O(n)，空间复杂度为O(1)），并且实现简单。在大多数情况下，简单的解决方案在保持代码清晰和易于维护方面是更好的选择。
单次遍历的策略在性能上表现良好，即使是在输入字符串长度接近上限的情况下。时间复杂度为O(n)，意味着处理时间与输入字符串的长度成线性关系。对于长度达到10^5的字符串，这种线性时间复杂度的算法是适合的，因为处理时间仍然在可接受范围内。