LeetCode 题解工作台
第一个出现两次的字母
给你一个由小写英文字母组成的字符串 s ，请你找出并返回第一个出现 两次 的字母。 注意： 如果 a 的 第二次 出现比 b 的 第二次 出现在字符串中的位置更靠前，则认为字母 a 在字母 b 之前出现两次。 s 包含至少一个出现两次的字母。 示例 1： 输入： s = "abccbaacz" 输出…
4
题型
8
代码语言
3
相关题
当前训练重点
简单 · 哈希·表·结合·string
答案摘要
遍历字符串 ，用数组或哈希表 `cnt` 记录每个字母出现的次数，当某个字母出现两次时，返回该字母。 时间复杂度 ，空间复杂度 。其中 为字符串 的长度，而 为字符集大小。本题中 $C = 26$。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 哈希·表·结合·string 题型思路
题目描述
给你一个由小写英文字母组成的字符串 s ，请你找出并返回第一个出现 两次 的字母。
注意：
- 如果
a的 第二次 出现比b的 第二次 出现在字符串中的位置更靠前，则认为字母a在字母b之前出现两次。 s包含至少一个出现两次的字母。
示例 1：
输入：s = "abccbaacz" 输出："c" 解释： 字母 'a' 在下标 0 、5 和 6 处出现。 字母 'b' 在下标 1 和 4 处出现。 字母 'c' 在下标 2 、3 和 7 处出现。 字母 'z' 在下标 8 处出现。 字母 'c' 是第一个出现两次的字母，因为在所有字母中，'c' 第二次出现的下标是最小的。
示例 2：
输入：s = "abcdd" 输出："d" 解释： 只有字母 'd' 出现两次，所以返回 'd' 。
提示：
2 <= s.length <= 100s由小写英文字母组成s包含至少一个重复字母
解题思路
方法一：数组或哈希表
遍历字符串 ，用数组或哈希表 cnt 记录每个字母出现的次数，当某个字母出现两次时，返回该字母。
时间复杂度 ，空间复杂度 。其中 为字符串 的长度，而 为字符集大小。本题中 。
class Solution:
def repeatedCharacter(self, s: str) -> str:
cnt = Counter()
for c in s:
cnt[c] += 1
if cnt[c] == 2:
return c
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) where n is the length of the string, since each character is processed once. Space complexity is O(1) if using a 26-bit mask or O(k) for a hash set with k unique letters. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Looking for O(n) solution using a hash table or bitmask.
- question_mark
Expect early return as soon as a repeat is detected.
- question_mark
Consider edge cases with multiple repeated letters.
常见陷阱
外企场景- error
Returning the first seen character instead of the first to repeat.
- error
Failing to handle strings where the repeated character is at the end.
- error
Using nested loops, resulting in O(n^2) time instead of O(n).
进阶变体
外企场景- arrow_right_alt
Return the first character to appear k times instead of twice.
- arrow_right_alt
Find the first repeated substring of length 2 or more.
- arrow_right_alt
Determine the last character to repeat instead of the first.