Hard

题目描述

字符串的方差定义为字符串中任意两个字符出现次数的最大差值。注意这两个字符可以相同，也可以不同。

给定一个只包含小写英文字母的字符串 s，返回 s 的所有子字符串中可能的最大方差。

子字符串是字符串中的一个连续字符序列。

示例 1：

输入：s = "aababbb"
输出：3
解释：
所有可能的方差及其对应的子字符串如下所示：
- 方差为 0 的子字符串："a", "aa", "ab", "abab", "aababb", "ba", "b", "bb", "bbb"。
- 方差为 1 的子字符串："aab", "aba", "abb", "aabab", "ababb", "aababbb", "bab"。
- 方差为 2 的子字符串："aaba", "ababbb", "abbb", "babb"。
- 方差为 3 的子字符串："babbb"。
由于最大可能方差为 3，所以返回 3。

示例 2：

输入：s = "abcde"
输出：0
解释：
s 中没有字母出现超过一次，所以每个子字符串的方差都是 0。

约束条件：

  • 1 <= s.length <= 10^4
  • s 只包含小写英文字母

解题思路

这道题的核心思想是将问题转化为Kadane算法的变种。

主要思路：

  1. 枚举字符对：枚举所有可能的字符对 (major, minor)，其中 major 是出现次数较多的字符，minor 是出现次数较少的字符。

  2. 转化为数组问题：将字符串转化为数值数组，major 字符记为 +1，minor 字符记为 -1，其他字符记为 0。这样方差就转化为了子数组的最大和。

  3. 使用Kadane算法的变种：需要确保子字符串中至少包含一个 minor 字符，否则方差为 0。维护两个状态：

    • hasMinor = false：当前子数组还没有遇到 minor 字符
    • hasMinor = true：当前子数组已经包含了 minor 字符

  4. 状态转移：

    • 遇到 major：两种状态的和都增加 1
    • 遇到 minor：hasMinor = false 状态转为 hasMinor = true，和变为 -1；hasMinor = true 状态的和减少 1
    • 遇到其他字符：保持不变

  5. 重置条件：当 hasMinor = true 的状态和变为负数时，重置为 0，但保持 hasMinor = true 状态。

这种方法确保我们能够找到包含指定字符对的子字符串的最大方差。

代码实现

class Solution {
public:
    int largestVariance(string s) {
        vector<int> counter(26, 0);
        for (char c : s) {
            counter[c - 'a']++;
        }
        
        int maxVariance = 0;
        
        for (int major = 0; major < 26; major++) {
            for (int minor = 0; minor < 26; minor++) {
                if (major == minor || counter[major] == 0 || counter[minor] == 0) {
                    continue;
                }
                
                int maxEndingHere = 0;
                int maxSoFar = 0;
                bool hasMinor = false;
                bool firstMinor = false;
                
                for (char c : s) {
                    if (c == 'a' + major) {
                        maxEndingHere++;
                    } else if (c == 'a' + minor) {
                        hasMinor = true;
                        firstMinor = true;
                        maxEndingHere--;
                    }
                    
                    if (hasMinor) {
                        maxSoFar = max(maxSoFar, maxEndingHere);
                    }
                    
                    if (maxEndingHere < 0 && hasMinor) {
                        maxEndingHere = 0;
                        hasMinor = false;
                    }
                }
                
                maxVariance = max(maxVariance, maxSoFar);
            }
        }
        
        return maxVariance;
    }
};

class Solution:
    def largestVariance(self, s: str) -> int:
        counter = [0] * 26
        for c in s:
            counter[ord(c) - ord('a')] += 1
        
        max_variance = 0
        
        for major in range(26):
            for minor in range(26):
                if major == minor or counter[major] == 0 or counter[minor] == 0:
                    continue
                
                max_ending_here = 0
                max_so_far = 0
                has_minor = False
                first_minor = False
                
                for c in s:
                    if ord(c) - ord('a') == major:
                        max_ending_here += 1
                    elif ord(c) - ord('a') == minor:
                        has_minor = True
                        first_minor = True
                        max_ending_here -= 1
                    
                    if has_minor:
                        max_so_far = max(max_so_far, max_ending_here)
                    
                    if max_ending_here < 0 and has_minor:
                        max_ending_here = 0
                        has_minor = False
        
                max_variance = max(max_variance, max_so_far)
        
        return max_variance

public class Solution {
    public int LargestVariance(string s) {
        int[] counter = new int[26];
        foreach (char c in s) {
            counter[c - 'a']++;
        }
        
        int maxVariance = 0;
        
        for (int major = 0; major < 26; major++) {
            for (int minor = 0; minor < 26; minor++) {
                if (major == minor || counter[major] == 0 || counter[minor] == 0) {
                    continue;
                }
                
                int maxEndingHere = 0;
                int maxSoFar = 0;
                bool hasMinor = false;
                bool firstMinor = false;
                
                foreach (char c in s) {
                    if (c == 'a' + major) {
                        maxEndingHere++;
                    } else if (c == 'a' + minor) {
                        hasMinor = true;
                        firstMinor = true;
                        maxEndingHere--;
                    }
                    
                    if (hasMinor) {
                        maxSoFar = Math.Max(maxSoFar, maxEndingHere);
                    }
                    
                    if (maxEndingHere < 0 && hasMinor) {
                        maxEndingHere = 0;
                        hasMinor = false;
                    }
                }
                
                maxVariance = Math.Max(maxVariance, maxSoFar);
            }
        }
        
        return maxVariance;
    }
}

var largestVariance = function(s) {
    const chars = [...new Set(s)];
    let maxVariance = 0;
    
    for (let i = 0; i < chars.length; i++) {
        for (let j = 0; j < chars.length; j++) {
            if (i === j) continue;
            
            const char1 = chars[i];
            const char2 = chars[j];
            
            let count1 = 0, count2 = 0;
            let hasChar2 = false;
            
            for (let k = 0; k < s.length; k++) {
                if (s[k] === char1) count1++;
                if (s[k] === char2) {
                    count2++;
                    hasChar2 = true;
                }
                
                if (hasChar2) {
                    maxVariance = Math.max(maxVariance, count1 - count2);
                }
                
                if (count1 < count2) {
                    count1 = 0;
                    count2 = 0;
                    hasChar2 = false;
                }
            }
        }
    }
    
    return maxVariance;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(26² × n) = O(n)
空间复杂度O(1)

其中 n 是字符串的长度。虽然有两层循环枚举字符对，但由于只有26个小写字母，所以常数因子为 26² = 676，整体时间复杂度仍为线性。

相关题目