Easy

题目描述

如果字符串中的每个字母在大写和小写形式下都出现，那么这个字符串是优美的。例如，“abABB” 是优美的，因为 ‘A’ 和 ‘a’ 都出现了，‘B’ 和 ‘b’ 也都出现了。但是 “abA” 不是优美的，因为 ‘b’ 出现了而 ‘B’ 没有出现。

给你一个字符串 s，返回 s 中最长的优美子字符串。如果有多个答案，返回最早出现的一个。如果不存在优美字符串，返回空字符串。

示例 1：

输入：s = "YazaAay"
输出："aAa"
解释："aAa" 是一个优美字符串，因为 s 中只有字母 'A/a'，并且 'A' 和 'a' 都出现了。
"aAa" 是最长的优美子字符串。

示例 2：

输入：s = "Bb"
输出："Bb"
解释："Bb" 是优美字符串，因为 'B' 和 'b' 都出现了。整个字符串就是一个子字符串。

示例 3：

输入：s = "c"
输出：""
解释：没有优美子字符串。

提示：

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

解题思路

这道题有多种解法，我们来分析几种常见的方法：

方法一：暴力枚举（推荐） 由于字符串长度最大为100，我们可以枚举所有可能的子字符串，然后检查每个子字符串是否为优美的。

判断优美字符串的逻辑：

  • 统计子字符串中出现的所有字符
  • 对于每个出现的字母，检查它的大写和小写形式是否都存在
  • 如果所有字母都满足条件，则该子字符串是优美的

方法二：分治法 如果一个字符只有大写或小写形式存在，那么包含该字符的子字符串都不可能是优美的。我们可以以这样的字符为分割点，递归处理左右两部分。

方法三：滑动窗口 可以尝试用滑动窗口，但实现较复杂，且对于这道题的数据规模，暴力法已经足够高效。

考虑到代码简洁性和易理解性，推荐使用方法一。时间复杂度为O(n³)，但由于n≤100，完全可以接受。

代码实现

class Solution {
public:
    string longestNiceSubstring(string s) {
        int n = s.length();
        string result = "";
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                string substr = s.substr(i, j - i + 1);
                if (isNice(substr) && substr.length() > result.length()) {
                    result = substr;
                }
            }
        }
        
        return result;
    }
    
private:
    bool isNice(const string& s) {
        unordered_set<char> chars(s.begin(), s.end());
        
        for (char c : chars) {
            if (isalpha(c)) {
                char upper = toupper(c);
                char lower = tolower(c);
                if (chars.find(upper) == chars.end() || chars.find(lower) == chars.end()) {
                    return false;
                }
            }
        }
        
        return true;
    }
};

class Solution:
    def longestNiceSubstring(self, s: str) -> str:
        def is_nice(substring):
            chars = set(substring)
            for c in chars:
                if c.upper() not in chars or c.lower() not in chars:
                    return False
            return True
        
        result = ""
        n = len(s)
        
        for i in range(n):
            for j in range(i + 1, n):
                substr = s[i:j+1]
                if is_nice(substr) and len(substr) > len(result):
                    result = substr
        
        return result

public class Solution {
    public string LongestNiceSubstring(string s) {
        string result = "";
        int n = s.Length;
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                string substr = s.Substring(i, j - i + 1);
                if (IsNice(substr) && substr.Length > result.Length) {
                    result = substr;
                }
            }
        }
        
        return result;
    }
    
    private bool IsNice(string s) {
        HashSet<char> chars = new HashSet<char>(s);
        
        foreach (char c in chars) {
            char upper = char.ToUpper(c);
            char lower = char.ToLower(c);
            if (!chars.Contains(upper) || !chars.Contains(lower)) {
                return false;
            }
        }
        
        return true;
    }
}

var longestNiceSubstring = function(s) {
    function isNice(substring) {
        const chars = new Set(substring);
        for (const c of chars) {
            if (!chars.has(c.toUpperCase()) || !chars.has(c.toLowerCase())) {
                return false;
            }
        }
        return true;
    }
    
    let result = "";
    const n = s.length;
    
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            const substr = s.substring(i, j + 1);
            if (isNice(substr) && substr.length > result.length) {
                result = substr;
            }
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n³)需要枚举所有子字符串O(n²)，每次检查是否优美需要O(n)
空间复杂度O(k)k为字符串中不同字符的数量，用于存储字符集合，最多26×2=52个字符

相关题目