2351. 第一个出现两次的字母

🟢   🔖  位运算 哈希表 字符串 计数  🔗 力扣 LeetCode

题目

Given a string s consisting of lowercase English letters, return the first letter to appear twice.

Note :

• A letter a appears twice before another letter b if the second occurrence of a is before the second occurrence of b.
• s will contain at least one letter that appears twice.

Example 1:

Input: s = "abccbaacz"

Output: "c"

Explanation:

The letter 'a' appears on the indexes 0, 5 and 6.

The letter 'b' appears on the indexes 1 and 4.

The letter 'c' appears on the indexes 2, 3 and 7.

The letter 'z' appears on the index 8.

The letter 'c' is the first letter to appear twice, because out of all the letters the index of its second occurrence is the smallest.

Example 2:

Input: s = "abcdd"

Output: "d"

Explanation:

The only letter that appears twice is 'd' so we return 'd'.

Constraints:

• 2 <= s.length <= 100
• s consists of lowercase English letters.
• s has at least one repeated letter.

题目大意

给你一个由小写英文字母组成的字符串 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 <= 100
• s 由小写英文字母组成
• s 包含至少一个重复字母

解题思路

如果字符串只包含小写字母，还可以用数组模拟哈希表来优化空间消耗：

1. 初始化一个长度为 26 的数组，用于存储已访问的字符的出现次数，模拟哈希表，优化空间。
2. 遍历字符串 s 的每个字符 char：
   • 使用 char.charCodeAt() - 97 获取字母在数组中对应的下标。
   • 如果 char 对应的数组元素大于 0，说明它是第一个重复的字符，立即返回。
   • 否则，将其对应的数组元素加一。
3. 遍历完成，返回找到的字符。

复杂度分析

• 时间复杂度： O(n)。
• 空间复杂度： O(1)（固定大小的数组）。

代码

/**
 * @param {string} s
 * @return {character}
 */
var repeatedCharacter = function (s) {
	let freq = new Array(26).fill(0);
	for (let char of s) {
		const index = char.charCodeAt() - 97;
		if (freq[index] > 0) return char;
		freq[index]++;
	}
};

相关题目

题号	标题	题解	标签	难度	力扣
1	两数之和	[✓]	数组 哈希表	🟢	🀄️ 🔗
387	字符串中的第一个唯一字符	[✓]	队列 哈希表 字符串 1+	🟢	🀄️ 🔗