题目描述
给你一个字符串 word
。如果 word
中同时出现某个字母 c
的小写形式和大写形式,并且 每个 小写形式的 c
都出现在第一个大写形式的 c
之前,则称字母 c
是一个 特殊字母。
返回 word
中 特殊字母 的数量。
样例
输入:word = "aaAbcBC"
输出:3
解释:
特殊字母是 'a'、'b' 和 'c'。
输入:word = "abc"
输出:0
解释:
word 中不存在特殊字母。
输入:word = "AbBCab"
输出:0
解释:
word 中不存在特殊字母。
限制
1 <= word.length <= 2 * 10^5
word
仅由小写和大写英文字母组成。
算法
(哈希表) $O(n + |\Sigma|)$
- 定义两个哈希表,分别存储小写字母和大写字母。其中每个小写字母存储最大的位置,每个大写字母存储最小的位置。
- 遍历字符集,如果大小写字母同时出现,且小写字母的位置小于大写字母的位置,则累加答案。
时间复杂度
- 构造哈希表的时间复杂度为 $O(n)$。
- 遍历字符集确定答案的时间复杂度为 $O(|\Sigma|)$。
- 故总时间复杂度为 $O(n + |\Sigma|)$。
空间复杂度
- 需要 $O(|\Sigma|)$ 的额外空间存储哈希表。
C++ 代码
class Solution {
public:
int numberOfSpecialChars(string word) {
const int n = word.size();
unordered_map<char, int> s1, s2;
for (int i = 0; i < n; i++)
if (word[i] >= 'a' && word[i] <= 'z')
s1[word[i]] = i;
for (int i = n - 1; i >= 0; i--)
if (word[i] >= 'A' && word[i] <= 'Z')
s2[word[i]] = i;
int ans = 0;
for (char c = 'a'; c <= 'z'; c++)
if (s1.count(c) && s2.count(c - 'a' + 'A') && s1[c] < s2[c - 'a' + 'A'])
++ans;
return ans;
}
};
我正向统计大写字母数量,为什么不对呢?