[LeetCode] 每日一题 2272. 最大波动的子字符串

题目链接

https://leetcode.cn/problems/substring-with-largest-variance

题目描述

字符串的 波动 定义为子字符串中出现次数 最多 的字符次数与出现次数 最少 的字符次数之差。

给你一个字符串 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 。

示例 2

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

提示

• 1 <= s.length <= 10^4

• s  只包含小写英文字母。

解题思路

这道题的核心在于如何高效计算字符串所有子串的最大波动值。直接遍历所有子串并计算其波动值的暴力解法在长度较大时不可行，因此需要寻找优化方案

关键思路是枚举两个不同的字符，设定其中一个字符作为子串中出现次数最多的字符，另一个字符作为出现次数最少的字符。然后，我们可以将这两个字符的出现情况映射为 +1 和 -1，转换成一个求最小子数组和的问题，即在保证至少包含一次 -1 的情况下，求最大子数组和。这个转换借鉴了之前的动态规划问题最大子数组和的思路，能够在线性时间内完成计算

代码实现

class Solution {
    public int largestVariance(String s) {
        int ans = 0;
        char[] strArray = s.toCharArray();
        for (char i = 'a'; i <= 'z'; i++) {
            for (char j = 'a'; j <= 'z'; j++) {
                if (i == j) {
                    continue;
                }
                int temp = 0;
                int res = Integer.MIN_VALUE;
                for (char c : strArray) {
                    if (c == i) {
                        temp = Math.max(temp, 0) + 1;
                        res++;
                    } else if (c == j) {
                        temp = Math.max(temp, 0) - 1;
                        res = temp;
                    }
                    ans = Math.max(ans, res);
                }
            }
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：外层双重循环枚举 26×26 = 676 种字符对。每次枚举字符对后，需要一次遍历字符串，时间复杂度为 O(n)。

• 空间复杂度：O(1)

总结

这道题的关键是转换问题的思考方式，即从字符频率计算转换为最优子数组问题。通过枚举两个字符，转化为相对简单一些的求最大子数组和，我们能够在近似线性的时间复杂度内解决问题。相比暴力遍历所有子串的 O(n²) 或 O(n³) 复杂度，这种方法更加高效。

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。