Easy

题目描述

给你一个由小写英文字母组成的字符串 s ，请你找出并返回第一个出现 两次 的字母。

注意：

  • 如果字母 a 的第二次出现比字母 b 的第二次出现在更前面的位置，则认为字母 a 在字母 b 之前出现两次。
  • s 包含至少一个出现两次的字母。

示例 1：

输入：s = "abccbaacz"
输出："c"
解释：
字母 'a' 在下标 0、5 和 6 处出现。
字母 'b' 在下标 1 和 4 处出现。
字母 'c' 在下标 2、3 和 7 处出现。
字母 'z' 在下标 8 处出现。
字母 'c' 是第一个出现两次的字母，因为在所有字母中，它的第二次出现的下标是最小的。

示例 2：

输入：s = "abcdd"
输出："d"
解释：
只有字母 'd' 出现两次，所以我们返回 'd'。

提示：

  • 2 <= s.length <= 100
  • s 由小写英文字母组成
  • s 至少包含一个重复字母

解题思路

解题思路

这道题要求找到第一个出现两次的字母。关键是理解"第一个"的含义：指的是第二次出现位置最靠前的字母。

方法一：哈希集合（推荐）

最直观的解法是使用哈希集合来记录已经见过的字符：

  1. 从左到右遍历字符串
  2. 对于每个字符，检查是否已经在集合中
  3. 如果已存在，说明这是第二次出现，直接返回该字符
  4. 如果不存在，将字符加入集合

由于我们从左到右遍历，第一个满足条件的字符必然是"第二次出现位置最靠前"的字符。

方法二：数组计数

由于只有26个小写字母，也可以使用布尔数组来记录字符是否出现过，原理相同但空间效率更高。

方法三：位运算

使用一个整数的二进制位来表示26个字母是否出现过，空间复杂度最优。

时间复杂度都是O(n)，其中n是字符串长度。由于题目保证一定存在重复字符，最坏情况下需要遍历整个字符串。

代码实现

class Solution {
public:
    char repeatedCharacter(string s) {
        unordered_set<char> seen;
        for (char c : s) {
            if (seen.count(c)) {
                return c;
            }
            seen.insert(c);
        }
        return ' '; // 根据题意不会执行到这里
    }
};

class Solution:
    def repeatedCharacter(self, s: str) -> str:
        seen = set()
        for c in s:
            if c in seen:
                return c
            seen.add(c)

public class Solution {
    public char RepeatedCharacter(string s) {
        HashSet<char> seen = new HashSet<char>();
        foreach (char c in s) {
            if (seen.Contains(c)) {
                return c;
            }
            seen.Add(c);
        }
        return ' '; // 根据题意不会执行到这里
    }
}

/**
 * @param {string} s
 * @return {character}
 */
var repeatedCharacter = function(s) {
    const seen = new Set();
    for (const c of s) {
        if (seen.has(c)) {
            return c;
        }
        seen.add(c);
    }
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型哈希集合方法数组计数方法位运算方法
时间复杂度O(n)O(n)O(n)
空间复杂度O(k)O(1)O(1)

其中 n 是字符串长度，k 是不同字符的个数（最多26个）。推荐使用哈希集合方法，代码简洁且易于理解。

相关题目