1763. 最长的美好子字符串

问题描述

给定一个字符串 s，请你找出并返回 s 中最长的美好子字符串。美好子字符串定义为，包含小写和大写每种字母的个数相同，并且没有多余的字符。

解题思路

为了找到最长的美好子字符串，可以利用暴力解法生成所有可能的子串，并检查每个子串是否为美好子串。虽然这种方法不是最优的，但可以帮助我们理解问题的基本逻辑。

美好子字符串的检查方法

1. 计数字符:
   • 使用两个数组分别记录小写字母和大写字母的出现次数。
2. 比较字符出现次数:
   • 对于每个字符，检查其小写字母和大写字母的出现次数是否相同。

暴力解法的实现

1. 生成所有可能的子串:
   • 使用双重循环生成所有可能的子串。
2. 检查子串是否为美好子串:
   • 使用两个数组分别记录小写字母和大写字母的出现次数。
   • 比较小写字母和大写字母的出现次数，判断子串是否为美好子串。
3. 记录最长美好子串的长度:
   • 更新最长美好子串的长度。

代码实现

/**
 * @param {string} s
 * @return {string}
 */
var longestNiceSubstring = function (s) {
    let maxLength = 0;
    let longestNiceSubstr = '';

    // Helper function to check if a substring is nice
    function isNice(sub) {
        let lower = new Array(26).fill(0);
        let upper = new Array(26).fill(0);
        for (let char of sub) {
            if (char >= 'a' && char <= 'z') {
                lower[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
            } else {
                upper[char.charCodeAt(0) - 'A'.charCodeAt(0)]++;
            }
        }
        for (let i = 0; i < 26; i++) {
            if ((lower[i] > 0 && upper[i] == 0) || (lower[i] == 0 && upper[i] > 0)) {
                return false;
            }
        }
        return true;
    }

    // Generate all substrings and check for the nice property
    for (let i = 0; i < s.length; i++) {
        for (let j = i + 1; j <= s.length; j++) {
            let sub = s.slice(i, j);
            if (isNice(sub) && sub.length > maxLength) {
                maxLength = sub.length;
                longestNiceSubstr = sub;
            }
        }
    }

    return longestNiceSubstr;
};

复杂度分析

• 时间复杂度: O(n^3)，其中 n 是字符串的长度。双重循环生成所有子串需要 O(n^2) 次操作，检查每个子串是否为美好子串需要 O(n) 次操作。
• 空间复杂度: O(1)，主要用于存储字符的出现次数。

更高效的方法

暴力解法虽然可以解决问题，但在面对大规模输入时效率较低。可以考虑使用递归或分治法来优化算法，减少不必要的检查操作。这样可以将时间复杂度降低到 O(n log n)。