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

题目描述

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

解法

方法一：数组或哈希表

遍历字符串 \(s\)，用数组或哈希表 cnt 记录每个字母出现的次数，当某个字母出现两次时，返回该字母。

时间复杂度 \(O(n)\)，空间复杂度 \(O(C)\)。其中 \(n\) 为字符串 \(s\) 的长度，而 \(C\) 为字符集大小。本题中 \(C = 26\)。

Python3JavaC++GoTypeScriptRustPHPC

class Solution:
    def repeatedCharacter(self, s: str) -> str:
        cnt = Counter()
        for c in s:
            cnt[c] += 1
            if cnt[c] == 2:
                return c

class Solution {
    public char repeatedCharacter(String s) {
        int[] cnt = new int[26];
        for (int i = 0;; ++i) {
            char c = s.charAt(i);
            if (++cnt[c - 'a'] == 2) {
                return c;
            }
        }
    }
}

class Solution {
public:
    char repeatedCharacter(string s) {
        int cnt[26]{};
        for (int i = 0;; ++i) {
            if (++cnt[s[i] - 'a'] == 2) {
                return s[i];
            }
        }
    }
};

func repeatedCharacter(s string) byte {
    cnt := [26]int{}
    for i := 0; ; i++ {
        cnt[s[i]-'a']++
        if cnt[s[i]-'a'] == 2 {
            return s[i]
        }
    }
}

function repeatedCharacter(s: string): string {
    const vis = new Array(26).fill(false);
    for (const c of s) {
        const i = c.charCodeAt(0) - 'a'.charCodeAt(0);
        if (vis[i]) {
            return c;
        }
        vis[i] = true;
    }
    return ' ';
}

impl Solution {
    pub fn repeated_character(s: String) -> char {
        let mut vis = [false; 26];
        for &c in s.as_bytes() {
            if vis[(c - b'a') as usize] {
                return c as char;
            }
            vis[(c - b'a') as usize] = true;
        }
        ' '
    }
}

class Solution {
    /**
     * @param String $s
     * @return String
     */
    function repeatedCharacter($s) {
        for ($i = 0; ; $i++) {
            $hashtable[$s[$i]] += 1;
            if ($hashtable[$s[$i]] == 2) {
                return $s[$i];
            }
        }
    }
}

char repeatedCharacter(char* s) {
    int vis[26] = {0};
    for (int i = 0; s[i]; i++) {
        if (vis[s[i] - 'a']) {
            return s[i];
        }
        vis[s[i] - 'a']++;
    }
    return ' ';
}

方法二：位运算

我们也可以用一个整数 mask 记录每个字母是否出现过，其中 mask 的第 \(i\) 位表示第 \(i\) 个字母是否出现过。当某个字母出现两次时，返回该字母。

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

Python3JavaC++GoTypeScriptRustC

class Solution:
    def repeatedCharacter(self, s: str) -> str:
        mask = 0
        for c in s:
            i = ord(c) - ord('a')
            if mask >> i & 1:
                return c
            mask |= 1 << i

class Solution {
    public char repeatedCharacter(String s) {
        int mask = 0;
        for (int i = 0;; ++i) {
            char c = s.charAt(i);
            if ((mask >> (c - 'a') & 1) == 1) {
                return c;
            }
            mask |= 1 << (c - 'a');
        }
    }
}

class Solution {
public:
    char repeatedCharacter(string s) {
        int mask = 0;
        for (int i = 0;; ++i) {
            if (mask >> (s[i] - 'a') & 1) {
                return s[i];
            }
            mask |= 1 << (s[i] - 'a');
        }
    }
};

func repeatedCharacter(s string) byte {
    mask := 0
    for i := 0; ; i++ {
        if mask>>(s[i]-'a')&1 == 1 {
            return s[i]
        }
        mask |= 1 << (s[i] - 'a')
    }
}

function repeatedCharacter(s: string): string {
    let mask = 0;
    for (const c of s) {
        const i = c.charCodeAt(0) - 'a'.charCodeAt(0);
        if (mask & (1 << i)) {
            return c;
        }
        mask |= 1 << i;
    }
    return ' ';
}

impl Solution {
    pub fn repeated_character(s: String) -> char {
        let mut mask = 0;
        for &c in s.as_bytes() {
            if (mask & (1 << ((c - b'a') as i32))) != 0 {
                return c as char;
            }
            mask |= 1 << ((c - b'a') as i32);
        }
        ' '
    }
}

char repeatedCharacter(char* s) {
    int mask = 0;
    for (int i = 0; s[i]; i++) {
        if (mask & (1 << s[i] - 'a')) {
            return s[i];
        }
        mask |= 1 << s[i] - 'a';
    }
    return ' ';
}

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

题目描述

解法

方法一：数组或哈希表

方法二：位运算

评论