0387. First Unique Character in a String

题目信息

题号:

0387

难度:

Easy

主题:

字符串、字符频次、最早位置、零基下标

原题:

LeetCode 0387

重点:

唯一字符必须只出现一次、返回最靠左位置、下标从 0 开始、无结果返回 -1

题目重述

给定只包含小写英文字母的字符串 s,寻找第一个在整个字符串中只出现一次的字符,并返回它的零基下标。若所有字符都至少出现两次,返回 -1。

s 的长度位于 [1, 10^5]。所谓“第一个”按原字符串从左到右的位置判断,而不是按字母表顺序;题目返回下标,不返回字符本身。

自建示例

最左侧字符并不唯一:

输入:s = "swiss"
输出:1
解释:s 出现三次,w 和 i 各出现一次;最靠左的唯一字符是下标 1 的 w。

没有唯一字符:

输入:s = "aabbcc"
输出:-1
解释:每个字符都出现两次,不存在只出现一次的字符。

先统计全局频次,再按原顺序找

“唯一”必须依据整个字符串判断,不能在第一次扫描时看到某字符只出现一次就立即返回,因为后面可能还有相同字符。先统计 26 个字母的总次数,第二次从左到右找到第一个频次为 1 的位置,正好对应最靠左的唯一字符。

C++ 实现

class Solution {
public:
    int firstUniqChar(std::string s) {
        std::array<int, 26> frequency{};
        for (char c : s) ++frequency[c - 'a'];
        for (int i = 0; i < static_cast<int>(s.size()); ++i) {
            if (frequency[s[i] - 'a'] == 1) return i;
        }
        return -1;
    }
};

代码分析

第一次扫描建立的是全局事实,第二次扫描保留了位置顺序;没有唯一字符时完整扫描后返回 -1。时间复杂度为 O(n),额外空间为固定的 O(1)。