【LetMeFly】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 <= 104
s
只包含小写英文字母。
很不错的一道题。
解题方法:动态规划
做本题之前推荐先做一下53. 最大子数组和:
一个数组中元素有正有负,如何求其非空子数组和的最大值呢?
遍历数组并使用一个变量$cnt$统计即可。
对于当前元素a,可以选择在前面子数组的基础上加上这个元素($cnt + a$),也可以选择丢弃前面子数组而从这个元素重新开始($a$)。
因此有状态转移方程$cnt = \max(cnt + a, a)$。
本题如何转为多次的“最大子数组”呢?本题的子数组只需要考虑出现次数最多和出现次数最少的两个元素,因此我直接两层循环枚举所有的“最多元素a”和“最少元素b”不就行了吗?
假设出现次数最多的元素是a,出现次数最少的元素是b。因为我们最终求的是$count(a) - count(b)$,所以我们可以将a赋值为1,将b赋值为-1,其他元素直接无视(或赋值为0)。
之后按照“最大子数组和”的方式求解,是不是就可以了?
不可以,因为“最多次数的a减去最少次数的b”的前提是“子数组中出现了b”。若子数组中全是a,那么出现次数最少的元素并非0次,而是同样为a次。也就是说,我们还需要想办法保证子数组中出现了b。
“最大子数组和”我们使用了一个变量cnt,本题我们可以使用两个变量$mayNoB$和$hasB$,分别表示子数组中可能不包含b和子数组中一定包含b时的“最大波动”。
因为mayNoB代表的子数组可以出现B也可以不出现B,所以mayNoB就和“最大子数组和”一样,无脑$mayNoB = \max(mayNoB + t, t)$即可($t$是字符的映射值$1$或者$-1$或者$0$)。
但是hasB就比较有意思了,它要求子数组中必须有b,怎么办呢?也很好说,把hasB的初始值定义为“无穷小”就好了。
- 若当前元素为b,则$hasB = mayNoB$,因为$mayNoB$一旦包含当前元素b就一定$hasB$了(其实是$hasB = max(hasB, mayNoB)$,但由于“可能不包含b”一定不小于“必须包含b”,所以可以直接简写为$hasB=mayNoB$)
- 若当前元素为a,则$hasB += 1$(若从未出现过元素b,则hasB即使加一也仍是无穷小,不影响后续答案的更新)
更新答案$ans = max(ans, hasB)$
- 时间复杂度$O(len(s)\times C^2)$,其中$C=26$
- 空间复杂度$O(1)$
AC代码
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71
|
#ifdef _WIN32 #include "_[1,2]toVector.h" #endif
#ifdef FirstTry class Solution { public: int largestVariance(string s) { int ans = 0; for (int i = 0; i < 26; i++) { char a = i + 'a'; for (int j = 0; j < 26; j++) { char b = j + 'a'; int cnt = 0; bool hasB = false; for (char c : s) { if (c == a) { cnt++; } else if (c == b) { if (cnt - 1 >= 0) { cnt--; hasB = true; } else { cnt = 0; hasB = false; } } if (hasB) { ans = max(ans, cnt); } } } } return ans; } }; #else
class Solution { public: int largestVariance(string s) { int ans = 0; for (int i = 0; i < 26; i++) { char a = i + 'a'; for (int j = 0; j < 26; j++) { char b = j + 'a'; int mayNoB = 0, hasB = -10000000; for (char c : s) { if (c == a) { mayNoB = max(mayNoB + 1, 1); hasB++; } else if (c == b) { mayNoB = max(mayNoB - 1, -1); hasB = mayNoB; } ans = max(ans, hasB); } } } return ans; } }; #endif
|
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| ''' Author: LetMeFly Date: 2025-03-16 11:06:25 LastEditors: LetMeFly.xyz LastEditTime: 2025-03-16 11:09:05 ''' class Solution: def largestVariance(self, s: str) -> int: ans = 0 for i in range(26): a = chr(i + ord('a')) for j in range(26): b = chr(j + ord('a')) mayNoB, hasB = 0, -100000 for c in s: if c == a: mayNoB = max(mayNoB + 1, 1) hasB += 1 elif c == b: mayNoB = max(mayNoB - 1, -1) hasB = mayNoB ans = max(ans, hasB) return ans
|
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
|
class Solution { public int largestVariance(String s) { int ans = 0; for (int i = 0; i < 26; i++) { char a = (char)(i + 'a'); for (int j = 0; j < 26; j++) { char b = (char)(j + 'a'); int mayNoB = 0, hasB = -10000000; for (char c : s.toCharArray()) { if (c == a) { mayNoB = Math.max(mayNoB + 1, 1); hasB++; } else if (c == b) { mayNoB = Math.max(mayNoB - 1, -1); hasB = mayNoB; } ans = Math.max(ans, hasB); } } } return ans; } }
|
Go
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
|
package main
func largestVariance(s string) (ans int) { for i := byte(0); i < 26; i++ { a := i + 'a' for j := byte(0); j < 26; j++ { b := j + 'a' mayNoB, hasB := 0, -10000000 for _, c := range s { if byte(c) == a { mayNoB = max(mayNoB + 1, 1) hasB++ } else if byte(c) == b { mayNoB = max(mayNoB - 1, -1) hasB = mayNoB } ans = max(ans, hasB) } } } return }
|
同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~
千篇源码题解已开源