LeetCode 2309题解：寻找字符串中的最大字母（哈希表+字符转换）
一、题目解读
LeetCode 2309题要求在一个仅含小写和/或大写英文字母的字符串中，找出满足以下条件的最大字母：该字母的大写和小写形式均出现在字符串中。例如，若输入 "aAbBcC"，则输出 "C"（大写 "C" 和小写 "c" 均存在）。题目难点在于高效判断字符对的存在性，并找到最大值。
二、解题思路
1. 使用无序集合（unordered_set<char> seen）存储所有出现过的字符，避免重复遍历。
2. 遍历字符串时，针对每个字符：
○ 若为大写，检查其对应小写字母是否在集合中；
○ 若为小写，检查大写字母是否存在。
3. 若字符对存在且当前字符大于当前最佳字母，则更新最佳字母。
4. 最终返回最佳字母的大写形式（若为空则返回空字符串）。
三、解题步骤
1. 初始化：
○ 创建哈希集合 seen 存储字符，初始化最佳字母 best 为空字符（'\0'）。
2. 遍历字符串，对每个字符 c，加入 seen 集合（seen.insert(c)）。
若 c 为大写：
转换小写 lower = tolower(c)，检查 lower 是否在 seen 中。
若存在且 c > best，更新 best。
若 c 为小写：
转换大写 upper = toupper(c)，检查 upper 是否在 seen 中。
若存在且 upper > best，更新 best。
3. 结果处理：
○ 若 best 为空，返回空字符串；否则将 best 转换为单字符字符串返回。
四、代码及注释
class Solution {
public:
string greateSTLetter(string s) {
unordered_set<char> seen; // 存储所有出现过的字符
char best = '\0'; // 初始化最佳字母为空字符
// 遍历字符串中的每个字符
for (char c : s) {
seen.insert(c); // 将当前字符加入集合
// 检查当前字符的大写和小写形式是否都在集合中
if (isupper(c)) { // 若为大写
char lower = tolower(c);
if (seen.count(lower) && c > best) {
best = c; // 更新最佳字母
}
} else { // 若为小写
char upper = toupper(c);
if (seen.count(upper) && upper > best) {
best = upper; // 更新最佳字母
}
}
}
// 若找到了最佳字母，返回其大写形式，否则返回空字符串
return best == '\0'? "" : string(1, best);
}
};五、总结
本解法通过哈希表高效记录字符出现情况，结合字符转换判断配对关系，时间复杂度为 O(n)，空间复杂度为 O(|Σ|)（Σ为字符集，实际为26个字母）。关键点包括：
1. 利用哈希集合减少重复查找；
2. 通过 isupper() 与 tolower()/toupper() 函数灵活处理大小写转换；
3. 边遍历边更新最佳字母，无需额外排序或遍历比较。
该算法简洁高效，适用于字符配对查找与最值求解场景，是处理字符串中字符关系问题的典型思路。
原创内容 转载请注明出处
