What is the largest variance in a substring?

The largest variance is the greatest difference in the frequency of any two distinct characters in a substring. For example, in 'aababbb', the largest variance is 3, which occurs in 'babbb'.

How can dynamic programming help solve this problem?

Dynamic programming can be used to track the frequency differences between characters in substrings and update them efficiently, reducing unnecessary recalculations.

What is the primary pattern used in 'Substring With Largest Variance'?

The primary pattern used is state transition dynamic programming, where we track the differences in character frequencies as we move through the string.

How do you handle substrings with more than two characters?

Start by considering substrings with two distinct characters to simplify the problem, then extend the solution to handle all characters without losing efficiency.

What are the time and space complexities of this solution?

The time complexity is O(n * k^2), where n is the length of the string and k is the number of distinct characters. The space complexity is O(1), as no additional space proportional to the input is used.

#2272

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

最大波动的子字符串

字符串的波动定义为子字符串中出现次数最多的字符次数与出现次数最少的字符次数之差。给你一个字符串 s ，它只包含小写英文字母。请你返回 s 里所有子字符串的最大波动值。子字符串是一个字符串的一段连续字符序列。示例 1：输入： s = "aababbb" 输出： 3 解释： …

数组动态规划

题目描述

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

给你一个字符串 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 只包含小写英文字母。

lightbulb

解题思路

方法一：枚举 + 动态规划

由于字符集只包含小写字母，我们可以考虑枚举出现次数最多的字符 $a$ 以及出现次数最少的字符 $b$ 。对于一个子串来说，这两种字符出现的次数之差就是子串的波动值。

具体实现上，我们使用双重循环枚举 $a$ 和 $b$ ，用 $f[0]$ 记录以当前字符结尾的连续出现字符 $a$ 的个数，用 $f[1]$ 记录以当前字符结尾的，并且包含 $a$ 和 $b$ 的子串的波动值。迭代取 $f[1]$ 的最大值即可。

递推公式如下：

如果当前字符为 $a$ ，则 $f[0]$ 和 $f[1]$ 都加 $1$ ；
如果当前字符为 $b$ ，则 $f[1] = \max(f[1] - 1, f[0] - 1)$ ，而 $f[0] = 0$ ；
否则，无需考虑。

注意，初始时将 $f[1]$ 赋值为一个负数最大值，可以保证更新答案时是合法的。

时间复杂度 $O(n \times |\Sigma|^2)$ ，其中 $n$ 是字符串长度，而 $|\Sigma|$ 是字符集大小。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def largestVariance(self, s: str) -> int:
        ans = 0
        for a, b in permutations(ascii_lowercase, 2):
            if a == b:
                continue
            f = [0, -inf]
            for c in s:
                if c == a:
                    f[0], f[1] = f[0] + 1, f[1] + 1
                elif c == b:
                    f[1] = max(f[1] - 1, f[0] - 1)
                    f[0] = 0
                if ans < f[1]:
                    ans = f[1]
        return ans

speed

复杂度分析

指标	值
时间	O(n \cdot k^2)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Look for understanding of dynamic programming and state transitions.
question_mark
Check if the candidate can optimize by considering only two characters initially.
question_mark
Assess whether the candidate uses iterative updates to minimize redundant calculations.

warning

常见陷阱

外企场景

error
Forgetting to optimize by limiting the number of distinct characters considered initially.
error
Overcomplicating the solution by recalculating character frequencies for every substring.
error
Neglecting the importance of updating states incrementally in dynamic programming.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the string contains more than two characters? Extend the solution to account for all characters while maintaining efficiency.
arrow_right_alt
Consider solving the problem without using dynamic programming and assess the trade-offs in terms of time complexity.
arrow_right_alt
Explore edge cases where the string is very short or where all characters are identical.

help

常见问题

外企场景

继续练习

#2267 检查是否有合法括号字符串路径 #2304 网格中的最小路径代价 #2305 公平分发饼干