Easy

题目描述

给你一个由英文字母组成的字符串 s，请你找出并返回 s 中的 最大的英文字母，该字母在 s 中必须同时以小写和大写形式出现。返回的字母应该用大写形式表示。如果不存在这样的字母，则返回一个空字符串。

英文字母 b 比另一个字母 a 更大的条件是：b 在英文字母表中出现在 a 之后。

示例 1：

输入：s = "lEeTcOdE"
输出："E"
解释：字母 'E' 是唯一一个既以小写又以大写形式出现的字母。

示例 2：

输入：s = "arRAzFif"
输出："R"
解释：字母 'R' 是同时以小写和大写形式出现的最大字母。
注意 'A' 和 'F' 也同时以小写和大写形式出现，但是 'R' 比 'F' 和 'A' 都大。

示例 3：

输入：s = "AbCdEfGhIjK"
输出：""
解释：不存在同时以小写和大写形式出现的字母。

提示：

  • 1 <= s.length <= 1000
  • s 由小写和大写英文字母组成

解题思路

解题思路

这道题要求找出字符串中同时以大写和小写形式出现的最大字母。我们可以考虑以下几种解法：

方法一：哈希表统计（推荐）

使用哈希表或集合记录所有出现过的字符，然后从 Z 到 A 倒序检查每个字母的大写和小写形式是否都在集合中。这样可以直接找到最大的符合条件的字母。

方法二：布尔数组

使用两个布尔数组分别记录大写字母和小写字母的出现情况，然后从 Z 到 A 检查对应位置。

方法三：位运算

使用两个整数的二进制位来表示26个字母的出现情况，通过位运算来判断。

第一种方法最直观易懂，代码简洁，是推荐解法。核心思想是：

  1. 遍历字符串，将所有字符存入集合
  2. 从 ‘Z’ 到 ‘A’ 倒序检查每个字母
  3. 如果某个字母的大写和小写形式都在集合中，直接返回该大写字母
  4. 如果遍历完都没找到，返回空字符串

时间复杂度为 O(n)，空间复杂度为 O(1)（最多存储52个字符）。

代码实现

class Solution {
public:
    string greatestLetter(string s) {
        unordered_set<char> seen(s.begin(), s.end());
        
        for (char c = 'Z'; c >= 'A'; c--) {
            if (seen.count(c) && seen.count(c + 32)) {
                return string(1, c);
            }
        }
        
        return "";
    }
};

class Solution:
    def greatestLetter(self, s: str) -> str:
        seen = set(s)
        
        for c in range(ord('Z'), ord('A') - 1, -1):
            upper = chr(c)
            lower = chr(c + 32)
            if upper in seen and lower in seen:
                return upper
        
        return ""

public class Solution {
    public string GreatestLetter(string s) {
        HashSet<char> seen = new HashSet<char>(s);
        
        for (char c = 'Z'; c >= 'A'; c--) {
            if (seen.Contains(c) && seen.Contains((char)(c + 32))) {
                return c.ToString();
            }
        }
        
        return "";
    }
}

var greatestLetter = function(s) {
    const seen = new Set(s);
    
    for (let i = 25; i >= 0; i--) {
        const upper = String.fromCharCode(65 + i);
        const lower = String.fromCharCode(97 + i);
        if (seen.has(upper) && seen.has(lower)) {
            return upper;
        }
    }
    
    return "";
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历字符串一次建立集合，然后最多检查26个字母
空间复杂度O(1)集合最多存储52个不同字符（26个大写+26个小写），为常数空间

相关题目