题目描述
LeetCode 3121 — 统计特殊字母的数量 II (Medium)
给定一个字符串 word，如果一个字母的大小写形式都出现在 word 中，并且所有小写出现都在第一个大写出现之前，则称该字母为特殊字母。返回特殊字母的数量。
示例 1：
- 输入：
word = "aaAbcBC" - 输出：
3 - 解释：
'a'、'b'、'c'都是特殊字母。以'a'为例，小写出现在下标 0 和 1，大写'A'第一次在下标 3，所有小写都在大写之前。
示例 2：
- 输入：
word = "abc" - 输出：
0 - 解释：没有任何大写字母出现，不满足「大小写都出现」这个前提条件。
示例 3：
- 输入：
word = "AbBCab" - 输出：
0 - 解释：
'b'的小写出现在下标 2 和 5，但大写'B'第一次在下标 1——最后一个小写在大写之后，不满足条件。
约束：
1 <= word.length <= 2 * 10^5word仅由小写和大写英文字母组成
求解思路
判断一个字母是否特殊，需要确认两件事：它的大小写都出现过，且所有小写都在第一个大写之前。
不难想到，我们不需要记录每个小写字母出现的所有位置，只需要最后一个。因为如果最后一个小写字母都在第一个大写之前，那排在它前面的那些自然更靠左。
同理，对于大写字母，只需要记录第一个出现的位置就够了。
于是问题简化成一次遍历：小写字母不断覆盖更新最后出现位置，大写字母只在首次遇到时记录位置。遍历结束后，对 26 个字母逐个检查：如果它的 lastLower 和 firstUpper 都存在，且 lastLower < firstUpper，那就是一个特殊字母。
整个过程只需要两个长度为 26 的数组，判断逻辑也是一次常数扫描。
解法：哈希表
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
int numberOfSpecialChars(string word) {
int n = word.size();
// 记录每个小写字母最后一次出现的下标
vector<int> lastLower(26, -1);
// 记录每个大写字母第一次出现的下标
vector<int> firstUpper(26, -1);
for (int i = 0; i < n; i++) {
char c = word[i];
if ('a' <= c && c <= 'z') {
lastLower[c - 'a'] = i; // 不断覆盖，保留最后的
} else {
int idx = c - 'A';
if (firstUpper[idx] == -1) { // 只记录第一次
firstUpper[idx] = i;
}
}
}
int num = 0;
for (int i = 0; i < 26; i++) {
if (lastLower[i] != -1 && firstUpper[i] != -1) {
if (lastLower[i] < firstUpper[i]) {
num++;
}
}
}
return num;
}
};
复杂度： 时间 ，一次遍历字符串加一次 26 的常数扫描；空间 ，两个固定大小的数组。