Medium

题目描述

给你一个由小写英文字母组成的字符串 s。

如果一个子字符串中所有不同的字符出现的次数都相同，则称该子字符串是平衡的。

返回 s 中最长平衡子字符串的长度。

示例 1：

输入：s = "abbac"
输出：4
解释：
最长的平衡子字符串是 "abba"，因为不同字符 'a' 和 'b' 都恰好出现 2 次。

示例 2：

输入：s = "zzabccy"
输出：4
解释：
最长的平衡子字符串是 "zabc"，因为不同字符 'z'、'a'、'b' 和 'c' 都恰好出现 1 次。

示例 3：

输入：s = "aba"
输出：2
解释：
最长的平衡子字符串之一是 "ab"，因为不同字符 'a' 和 'b' 都恰好出现 1 次。另一个最长的平衡子字符串是 "ba"。

约束条件：

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

提示：

  • 对所有子字符串使用暴力枚举

解题思路

解题思路

这道题要求找到最长的平衡子字符串，其中平衡的定义是所有不同字符出现的次数都相同。

由于字符串长度最大为 1000，我们可以使用暴力枚举的方法来解决这个问题：

  1. 暴力枚举所有子字符串：遍历所有可能的起始位置和结束位置组合
  2. 统计字符频次：对于每个子字符串，使用哈希表统计各字符的出现次数
  3. 检查是否平衡：验证所有不同字符的出现次数是否相等
  4. 更新最大长度：如果当前子字符串平衡且长度更长，则更新结果

优化思路：

  • 在遍历过程中，我们可以动态维护字符频次，避免重复计算
  • 当发现某个子字符串不平衡时，可以适当剪枝

时间复杂度分析：

  • 外层两重循环：O(n²)
  • 内层检查平衡性：O(26) = O(1)
  • 总体时间复杂度：O(n²)

这种方法虽然看起来简单，但对于给定的约束条件（n ≤ 1000）是完全可行的，且实现清晰易懂。

代码实现

class Solution {
public:
    int longestBalanced(string s) {
        int n = s.length();
        int maxLen = 0;
        
        for (int i = 0; i < n; i++) {
            unordered_map<char, int> count;
            for (int j = i; j < n; j++) {
                count[s[j]]++;
                
                // Check if current substring is balanced
                int freq = count.begin()->second;
                bool balanced = true;
                for (auto& p : count) {
                    if (p.second != freq) {
                        balanced = false;
                        break;
                    }
                }
                
                if (balanced) {
                    maxLen = max(maxLen, j - i + 1);
                }
            }
        }
        
        return maxLen;
    }
};

class Solution:
    def longestBalanced(self, s: str) -> int:
        n = len(s)
        max_len = 0
        
        for i in range(n):
            count = {}
            for j in range(i, n):
                count[s[j]] = count.get(s[j], 0) + 1
                
                # Check if current substring is balanced
                frequencies = list(count.values())
                if len(set(frequencies)) == 1:
                    max_len = max(max_len, j - i + 1)
        
        return max_len

public class Solution {
    public int LongestBalanced(string s) {
        int n = s.Length;
        int maxLen = 0;
        
        for (int i = 0; i < n; i++) {
            var count = new Dictionary<char, int>();
            for (int j = i; j < n; j++) {
                if (count.ContainsKey(s[j])) {
                    count[s[j]]++;
                } else {
                    count[s[j]] = 1;
                }
                
                // Check if current substring is balanced
                var frequencies = count.Values.ToHashSet();
                if (frequencies.Count == 1) {
                    maxLen = Math.Max(maxLen, j - i + 1);
                }
            }
        }
        
        return maxLen;
    }
}

var longestBalanced = function(s) {
    let maxLen = 0;
    
    for (let i = 0; i < s.length; i++) {
        let freq = {};
        
        for (let j = i; j < s.length; j++) {
            freq[s[j]] = (freq[s[j]] || 0) + 1;
            
            let counts = Object.values(freq);
            let firstCount = counts[0];
            let isBalanced = counts.every(count => count === firstCount);
            
            if (isBalanced) {
                maxLen = Math.max(maxLen, j - i + 1);
            }
        }
    }
    
    return maxLen;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²)两重循环遍历所有子字符串，每次检查平衡性为 O(26) = O(1)
空间复杂度O(1)哈希表最多存储 26 个字符，为常数空间