How do I extract digits from the string?

You can use Python's `isdigit()` method to identify and extract digits from the string.

What if there are fewer than two distinct digits?

In this case, return -1, as there is no second largest digit available.

What is the time complexity of the solution?

The time complexity is O(n + k log k), where n is the length of the string and k is the number of distinct digits.

Can I use a hash table for storing digits?

Yes, a hash table (or set) can be used to store distinct digits efficiently.

What happens if there are multiple occurrences of the same digit?

Only distinct digits should be considered when finding the second largest digit.

#1796

Easy

auto_awesome哈希·表·结合·string

LeetCode 题解工作台

字符串中第二大的数字

给你一个混合字符串 s ，请你返回 s 中第二大的数字，如果不存在第二大的数字，请你返回 -1 。混合字符串由小写英文字母和数字组成。示例 1：输入： s = "dfa12321afd" 输出： 2 解释：出现在 s 中的数字包括 [1, 2, 3] 。第二大的数字是 2 。示例 2…

哈希表字符串

题目描述

给你一个混合字符串 s ，请你返回 s 中 第二大 的数字，如果不存在第二大的数字，请你返回 -1 。

混合字符串 由小写英文字母和数字组成。

示例 1：

输入：s = "dfa12321afd"
输出：2
解释：出现在 s 中的数字包括 [1, 2, 3] 。第二大的数字是 2 。

示例 2：

输入：s = "abc1111"
输出：-1
解释：出现在 s 中的数字只包含 [1] 。没有第二大的数字。

提示：

1 <= s.length <= 500
s 只包含小写英文字母和（或）数字。

lightbulb

解题思路

方法一：一次遍历

我们定义 $a$ 和 $b$ 分别表示字符串中出现的最大数字和第二大数字，初始时 $a = b = -1$ 。

遍历字符串 $s$ ，如果当前字符是数字，我们将其转换为数字 $v$ ，如果 $v \gt a$ ，说明 $v$ 是当前出现的最大数字，我们将 $b$ 更新为 $a$ ，并将 $a$ 更新为 $v$ ；如果 $v \lt a$ ，说明 $v$ 是当前出现的第二大数字，我们将 $b$ 更新为 $v$ 。

遍历结束，返回 $b$ 即可。

时间复杂度 $O(n)$ ，其中 $n$ 为字符串 $s$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def secondHighest(self, s: str) -> int:
        a = b = -1
        for c in s:
            if c.isdigit():
                v = int(c)
                if v > a:
                    a, b = v, a
                elif b < v < a:
                    b = v
        return b

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for a solution that efficiently handles string parsing and digit extraction.
question_mark
Ensure the candidate considers edge cases such as no digits or only one digit.
question_mark
Expect a clear understanding of hash tables for removing duplicates and sorting for the second largest value.

warning

常见陷阱

外企场景

error
Failing to handle cases with fewer than two digits correctly.
error
Not accounting for the presence of non-digit characters in the string.
error
Incorrectly assuming there will always be at least two distinct digits.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the string contains non-digit characters only? How should the program behave?
arrow_right_alt
Consider the situation where there are multiple occurrences of the largest digit, but no second largest.
arrow_right_alt
What if the string has exactly two distinct digits? Ensure the program still returns the second largest.

help

常见问题

外企场景

继续练习

#1790 仅执行一次字符串交换能否使两个字符串相等 #1805 字符串中不同整数的数目 #1807 替换字符串中的括号内容