Medium

题目描述

给你一个只包含字符 ‘a’、‘b’ 和 ‘c’ 的字符串 s。

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

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

示例 1：

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

示例 2：

输入：s = "aabcc"
输出：3
解释：最长平衡子串是 "abc"，因为所有不同字符 'a'、'b' 和 'c' 都恰好出现 1 次。

示例 3：

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

约束条件：

  • 1 <= s.length <= 10^5
  • s 只包含字符 ‘a’、‘b’ 和 ‘c’

解题思路

这道题需要分三种情况来考虑：

情况1：单个字符 最长的平衡子串就是连续相同字符的最长序列，因为只有一个字符时它必然平衡。

情况2：两个不同字符 对于任意两个字符的组合，我们可以忽略第三个字符，只关注这两个字符。使用前缀和的差值来判断平衡性：如果在两个位置上两个字符的计数差值相同，那么这两个位置之间的子串是平衡的。

情况3：三个字符都存在 使用前缀计数和哈希表。我们用 (count_b - count_a, count_c - count_a) 作为键值，如果同样的键值在两个不同位置出现，说明这两个位置之间的子串中三个字符的出现次数相等。

核心思路是将问题分解为三个子问题，分别求解后取最大值。对于情况2和3，我们利用前缀和的性质：如果两个前缀的字符计数差值相同，那么它们之间的子串是平衡的。

代码实现

class Solution {
public:
    int longestBalanced(string s) {
        int n = s.length();
        int maxLen = 0;
        
        // Case 1: Single character
        int currentLen = 1;
        for (int i = 1; i < n; i++) {
            if (s[i] == s[i-1]) {
                currentLen++;
            } else {
                maxLen = max(maxLen, currentLen);
                currentLen = 1;
            }
        }
        maxLen = max(maxLen, currentLen);
        
        // Case 2: Two distinct characters
        vector<pair<char, char>> pairs = {{'a', 'b'}, {'a', 'c'}, {'b', 'c'}};
        for (auto& p : pairs) {
            char c1 = p.first, c2 = p.second;
            unordered_map<int, int> diffMap;
            diffMap[0] = -1;
            int diff = 0;
            for (int i = 0; i < n; i++) {
                if (s[i] == c1) diff++;
                else if (s[i] == c2) diff--;
                
                if (diffMap.count(diff)) {
                    maxLen = max(maxLen, i - diffMap[diff]);
                } else {
                    diffMap[diff] = i;
                }
            }
        }
        
        // Case 3: All three characters
        map<pair<int, int>, int> stateMap;
        stateMap[{0, 0}] = -1;
        int countA = 0, countB = 0, countC = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == 'a') countA++;
            else if (s[i] == 'b') countB++;
            else countC++;
            
            pair<int, int> state = {countB - countA, countC - countA};
            if (stateMap.count(state)) {
                maxLen = max(maxLen, i - stateMap[state]);
            } else {
                stateMap[state] = i;
            }
        }
        
        return maxLen;
    }
};

class Solution:
    def longestBalanced(self, s: str) -> int:
        n = len(s)
        max_len = 0
        
        # Case 1: Single character
        current_len = 1
        for i in range(1, n):
            if s[i] == s[i-1]:
                current_len += 1
            else:
                max_len = max(max_len, current_len)
                current_len = 1
        max_len = max(max_len, current_len)
        
        # Case 2: Two distinct characters
        pairs = [('a', 'b'), ('a', 'c'), ('b', 'c')]
        for c1, c2 in pairs:
            diff_map = {0: -1}
            diff = 0
            for i, char in enumerate(s):
                if char == c1:
                    diff += 1
                elif char == c2:
                    diff -= 1
                
                if diff in diff_map:
                    max_len = max(max_len, i - diff_map[diff])
                else:
                    diff_map[diff] = i
        
        # Case 3: All three characters
        state_map = {(0, 0): -1}
        count_a = count_b = count_c = 0
        for i, char in enumerate(s):
            if char == 'a':
                count_a += 1
            elif char == 'b':
                count_b += 1
            else:
                count_c += 1
            
            state = (count_b - count_a, count_c - count_a)
            if state in state_map:
                max_len = max(max_len, i - state_map[state])
            else:
                state_map[state] = i
        
        return max_len

public class Solution {
    public int LongestBalanced(string s) {
        int n = s.Length;
        int maxLen = 0;
        
        // Case 1: Single character
        int currentLen = 1;
        for (int i = 1; i < n; i++) {
            if (s[i] == s[i-1]) {
                currentLen++;
            } else {
                maxLen = Math.Max(maxLen, currentLen);
                currentLen = 1;
            }
        }
        maxLen = Math.Max(maxLen, currentLen);
        
        // Case 2: Two distinct characters
        char[,] pairs = {{'a', 'b'}, {'a', 'c'}, {'b', 'c'}};
        for (int p = 0; p < 3; p++) {
            char c1 = pairs[p, 0], c2 = pairs[p, 1];
            var diffMap = new Dictionary<int, int> {{0, -1}};
            int diff = 0;
            for (int i = 0; i < n; i++) {
                if (s[i] == c1) diff++;
                else if (s[i] == c2) diff--;
                
                if (diffMap.ContainsKey(diff)) {
                    maxLen = Math.Max(maxLen, i - diffMap[diff]);
                } else {
                    diffMap[diff] = i;
                }
            }
        }
        
        // Case 3: All three characters
        var stateMap = new Dictionary<(int, int), int> {[(0, 0)] = -1};
        int countA = 0, countB = 0, countC = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == 'a') countA++;
            else if (s[i] == 'b') countB++;
            else countC++;
            
            var state = (countB - countA, countC - countA);
            if (stateMap.ContainsKey(state)) {
                maxLen = Math.Max(maxLen, i - stateMap[state]);
            } else {
                stateMap[state] = i;
            }
        }
        
        return maxLen;
    }
}

var longestBalanced = function(s) {
    const n = s.length;
    let maxLen = 0;
    
    // Case 1: Single character
    let currentLen = 1;
    for (let i = 1; i < n; i++) {
        if (s[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n)
空间复杂度O(n)

其中 n 是字符串的长度。每种情况都只需要遍历字符串一次，哈希表的大小最多为 O(n)。