最大波动的子字符串

难度: 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 。

示例 2：

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

提示：

1 <= s.length <= 10⁴
s 只包含小写英文字母。

Submission

运行时间: 527 ms

内存: 16.0 MB

class Solution:
    def largestVariance(self, s: str) -> int:
        if s.count(s[0]) == len(s):
            return 0
        
        ans = 0
        diff = [[0] * 26 for _ in range(26)]
        diff_with_b = [[float("-inf")] * 26 for _ in range(26)]

        for ch in s:
            ch = ord(ch) - ord('a')
            for i in range(26):
                if i == ch:
                    continue
                diff[ch][i] += 1
                diff_with_b[ch][i] += 1

                diff[i][ch] -= 1
                diff_with_b[i][ch] = diff[i][ch]
                if diff[i][ch] < 0:
                    diff[i][ch] = 0
                ans = max(diff_with_b[ch][i], diff_with_b[i][ch], ans )
        return ans

Explain

这道题的解决方案使用了双层字母频率差分数组来跟踪任意两个字符的出现次数差异。首先，对于全由同一字符构成的字符串，波动值为0。接着，定义两个二维数组，分别用来记录每对字符在遍历过程中的次数差(diff)和含波动性的次数差(diff_with_b)。遍历字符串中的每个字符，并更新两个数组：如果当前字符是i，那么对于所有不等于i的j，增加diff[i][j]，减少diff[j][i]。若diff[j][i]变为负值，则重置为0，表示重新开始计算该对字符的差异。同时更新diff_with_b，该数组记录了包含至少一次波动性的最大次数差。最后，遍历完所有字符后，diff_with_b数组中的最大值即为答案。

时间复杂度: O(n)

空间复杂度: O(1)

# 添加注释的解题代码
class Solution:
    def largestVariance(self, s: str) -> int:
        if s.count(s[0]) == len(s):
            return 0  # 如果字符串中所有字符相同，波动值为0
        
        ans = 0  # 初始化最大波动值
        diff = [[0] * 26 for _ in range(26)]  # 字符对次数差
        diff_with_b = [[float("-inf")] * 26 for _ in range(26)]  # 包含波动的字符对次数差

        for ch in s:
            ch = ord(ch) - ord('a')  # 转换当前字符为索引
            for i in range(26):  # 遍历所有可能的字符对
                if i == ch:
                    continue  # 跳过自己与自己的比较
                diff[ch][i] += 1  # 增加当前字符的计数
                diff_with_b[ch][i] += 1  # 相同的增加操作

                diff[i][ch] -= 1  # 减少与当前字符对的其他字符计数
                diff_with_b[i][ch] = diff[i][ch]  # 更新含波动性的计数
                if diff[i][ch] < 0:
                    diff[i][ch] = 0  # 如果次数差为负，重置
                ans = max(diff_with_b[ch][i], diff_with_b[i][ch], ans)  # 更新最大波动值
        return ans  # 返回计算的最大波动值

Explore

在这个算法中，数组 `diff` 用于追踪任意两个不同字符之间的出现次数差。这个差值可以帮助我们理解两个字符在任意时间点的相对频率。数组 `diff_with_b` 则用于追踪包含至少一次波动（即一方至少比另一方多出现一次）的次数差的最大值。这种分开追踪的方式允许我们准确地计算出在任何时点字符出现的动态差异，并保持记录在何时某个字符对首次出现波动，这对于解决问题至关重要。

当 `diff[j][i]` 变为负值时，意味着在当前的字符序列中，字符 `i` 出现的次数比字符 `j` 更少。重置 `diff[j][i]` 为0是为了重新开始计数这两个字符的差异，忽略之前的负波动。这是因为我们只对正的波动值感兴趣（即一种字符比另一种多的情况），并且这种重置使我们能够关注从当前点开始的新的波动。同时更新 `diff_with_b[i][j]` 为 `diff[i][j]` 保证了我们记录的是包含至少一次波动的次数差的最大值，从而帮助我们找到可能的最大波动值。

在算法中，`diff_with_b[i][ch]` 记录的是从字符串开始到当前位置，包含至少一次波动的最大次数差。即使 `diff[i][ch]` 被重置为0，我们需要保留 `diff_with_b[i][ch]` 的值不变，因为该值代表了之前的最大波动，可能是整个字符串中的最大值。重置 `diff[i][ch]` 是为了重新开始计算新的波动，但这不影响之前已经达到的最大波动值。

该代码中的两层循环分别遍历字符串中的每个字符和26个可能的字母，导致算法的时间复杂度为O(n * 26)，其中n是字符串的长度。在最坏情况下，这种方法是有效的，因为每个字符都需要与其他25个字符进行比较来更新差异。尽管如此，考虑到实际字符的使用频率，可以对算法进行优化，例如只更新实际在字符串中出现的字符对，而不是固定的26个字母，这可能会减少不必要的计算并提高效率。