LeetCode 2272.最大波动的子字符串：转为多次的最大子数组和 - 一步步思考 ...

【LetMeFly】2272.最大波动的子字符串：转为多次的最大子数组和 - 一步步思考推导

力扣题目链接：https://leetcode.cn/problems/substring-with-largest-variance/
字符串的 波动 定义为子字符串中出现次数 最多 的字符次数与出现次数 最少 的字符次数之差。
给你一个字符串 s ，它只包含小写英文字母。请你返回 s 里所有 子字符串的 最大波动 值。
子字符串 是一个字符串的一段一连字符序列。
 
示例 1：

1. <b>输入：</b>s = "aababbb"
2. <b>输出：</b>3
3. <strong>解释：</strong>
4. 所有可能的波动值和它们对应的子字符串如以下所示：
5. - 波动值为 0 的子字符串："a" ，"aa" ，"ab" ，"abab" ，"aababb" ，"ba" ，"b" ，"bb" 和 "bbb" 。
6. - 波动值为 1 的子字符串："aab" ，"aba" ，"abb" ，"aabab" ，"ababb" ，"aababbb" 和 "bab" 。
7. - 波动值为 2 的子字符串："aaba" ，"ababbb" ，"abbb" 和 "babb" 。
8. - 波动值为 3 的子字符串 "babbb" 。
9. 所以，最大可能波动值为 3 。

复制代码

示例 2：

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

复制代码

 
提示：

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

解题方法：动态规划

做本题之前推荐先做一下53. 最大子数组和：
   一个数组中元素有正有负，怎样求其非空子数组和的最大值呢？
  遍历数组并使用一个变量                                        c                            n                            t                                  cnt                     cnt统计即可。
  对于当前元素a，可以选择在前面子数组的底子上加上这个元素(                                        c                            n                            t                            +                            a                                  cnt + a                     cnt+a)，也可以选择丢弃前面子数组而从这个元素重新开始(                                        a                                  a                     a)。
  因此有状态转移方程                                        c                            n                            t                            =                            max                            ⁡                            (                            c                            n                            t                            +                            a                            ,                            a                            )                                  cnt = \max(cnt + a, a)                     cnt=max(cnt+a,a)。
  本题怎样转为多次的“最大子数组”呢？本题的子数组只需要思量出现次数最多和出现次数最少的两个元素，因此我直接两层循环枚举所有的“最多元素a”和“最少元素b”不就行了吗？
   假设出现次数最多的元素是a，出现次数最少的元素是b。因为我们终极求的是                                        c                            o                            u                            n                            t                            (                            a                            )                            −                            c                            o                            u                            n                            t                            (                            b                            )                                  count(a) - count(b)                     count(a)−count(b)，所以我们可以将a赋值为1，将b赋值为-1，其他元素直接无视（或赋值为0）。
  之后按照“最大子数组和”的方式求解，是不是就可以了？
  不可以，因为“最多次数的a减去最少次数的b”的条件是“子数组中出现了b”。若子数组中全是a，那么出现次数最少的元素并非0次，而是同样为a次。也就是说，我们还需要想办法包管子数组中出现了b。
   “最大子数组和”我们使用了一个变量cnt，本题我们可以使用两个变量                                        m                            a                            y                            N                            o                            B                                  mayNoB                     mayNoB和                                        h                            a                            s                            B                                  hasB                     hasB，分别表现子数组中可能不包含b和子数组中肯定包含b时的“最大波动”。
  因为mayNoB代表的子数组可以出现B也可以不出现B，所以mayNoB就和“最大子数组和”一样，无脑                                        m                            a                            y                            N                            o                            B                            =                            max                            ⁡                            (                            m                            a                            y                            N                            o                            B                            +                            t                            ,                            t                            )                                  mayNoB = \max(mayNoB + t, t)                     mayNoB=max(mayNoB+t,t)即可（                                        t                                  t                     t是字符的映射值                                        1                                  1                     1大概                                        −                            1                                  -1                     −1大概                                        0                                  0                     0）。
  但是hasB就比较有意思了，它要求子数组中必须有b，怎么办呢？也很好说，把hasB的初始值定义为“无穷小”就好了。
  

• 若当前元素为b，则                                             h                               a                               s                               B                               =                               m                               a                               y                               N                               o                               B                                      hasB = mayNoB                        hasB=mayNoB，因为                                             m                               a                               y                               N                               o                               B                                      mayNoB                        mayNoB一旦包含当前元素b就肯定                                             h                               a                               s                               B                                      hasB                        hasB了（其实是                                             h                               a                               s                               B                               =                               m                               a                               x                               (                               h                               a                               s                               B                               ,                               m                               a                               y                               N                               o                               B                               )                                      hasB = max(hasB, mayNoB)                        hasB=max(hasB,mayNoB)，但由于“可能不包含b”肯定不小于“必须包含b”，所以可以直接简写为                                             h                               a                               s                               B                               =                               m                               a                               y                               N                               o                               B                                      hasB=mayNoB                        hasB=mayNoB）
  
• 若当前元素为a，则                                             h                               a                               s                               B                               +                               =                               1                                      hasB += 1                        hasB+=1（若从未出现过元素b，则hasB即使加一也还是无穷小，不影响后续答案的更新）
  

  更新答案                                        a                            n                            s                            =                            m                            a                            x                            (                            a                            n                            s                            ,                            h                            a                            s                            B                            )                                  ans = max(ans, hasB)                     ans=max(ans,hasB)
  

• 时间复杂度                                        O                            (                            l                            e                            n                            (                            s                            )                            ×                                       C                               2                                      )                                  O(len(s)\times C^2)                     O(len(s)×C2)，此中                                        C                            =                            26                                  C=26                     C=26
  
• 空间复杂度                                        O                            (                            1                            )                                  O(1)                     O(1)
  

AC代码

C++

1. /*
2. * @Author: LetMeFly
3. * @Date: 2025-03-16 10:43:25
4. * @LastEditors: LetMeFly.xyz
5. * @LastEditTime: 2025-03-16 11:03:26
6. */
7. #ifdef _WIN32
8. #include "_[1,2]toVector.h"
9. #endif
11. #ifdef FirstTry  // WA - 例如baa，一个变量会导致不选b，而只有aa虽然cnt比较大但不一定最优
12. class Solution {
13. public:
14.     int largestVariance(string s) {
15.         int ans = 0;
16.         for (int i = 0; i < 26; i++) {
17.             char a = i + 'a';
18.             for (int j = 0; j < 26; j++) {
19.                 char b = j + 'a';
20.                 int cnt = 0;
21.                 bool hasB = false;
22.                 for (char c : s) {
23.                     if (c == a) {
24.                         cnt++;
25.                     } else if (c == b) {
26.                         // cnt = max(cnt - 1, 0);
27.                         if (cnt - 1 >= 0) {
28.                             cnt--;
29.                             hasB = true;
30.                         } else {
31.                             cnt = 0;
32.                             hasB = false;
33.                         }
34.                     }
35.                     if (hasB) {
36.                         ans = max(ans, cnt);
37.                     }
38.                 }
39.                 // printf("a = %c, b = %c, ans = %d\n", a, b, ans);
40.             }
41.         }
42.         return ans;
43.     }
44. };
45. #else  // FirstTry
46. // SecondTry
47. class Solution {
48. public:
49.     int largestVariance(string s) {
50.         int ans = 0;
51.         for (int i = 0; i < 26; i++) {
52.             char a = i + 'a';
53.             for (int j = 0; j < 26; j++) {
54.                 char b = j + 'a';
55.                 int mayNoB = 0, hasB = -10000000;
56.                 for (char c : s) {
57.                     if (c == a) {
58.                         mayNoB = max(mayNoB + 1, 1);
59.                         hasB++;
60.                     } else if (c == b) {
61.                         mayNoB = max(mayNoB - 1, -1);
62.                         hasB = mayNoB;
63.                     }
64.                     ans = max(ans, hasB);
65.                 }
66.             }
67.         }
68.         return ans;
69.     }
70. };
71. #endif  // FirstTry

复制代码

Python

1. '''
2. Author: LetMeFly
3. Date: 2025-03-16 11:06:25
4. LastEditors: LetMeFly.xyz
5. LastEditTime: 2025-03-16 11:09:05
6. '''
7. class Solution:
8.     def largestVariance(self, s: str) -> int:
9.         ans = 0
10.         for i in range(26):
11.             a = chr(i + ord('a'))
12.             for j in range(26):
13.                 b = chr(j + ord('a'))
14.                 mayNoB, hasB = 0, -100000
15.                 for c in s:
16.                     if c == a:
17.                         mayNoB = max(mayNoB + 1, 1)
18.                         hasB += 1
19.                     elif c == b:
20.                         mayNoB = max(mayNoB - 1, -1)
21.                         hasB = mayNoB
22.                     ans = max(ans, hasB)
23.         return ans

复制代码

Java

1. /*
2. * @Author: LetMeFly
3. * @Date: 2025-03-16 11:09:39
4. * @LastEditors: LetMeFly.xyz
5. * @LastEditTime: 2025-03-16 11:13:27
6. */
7. class Solution {
8.     public int largestVariance(String s) {
9.         int ans = 0;
10.         for (int i = 0; i < 26; i++) {
11.             char a = (char)(i + 'a');
12.             for (int j = 0; j < 26; j++) {
13.                 char b = (char)(j + 'a');
14.                 int mayNoB = 0, hasB = -10000000;
15.                 for (char c : s.toCharArray()) {
16.                     if (c == a) {
17.                         mayNoB = Math.max(mayNoB + 1, 1);
18.                         hasB++;
19.                     } else if (c == b) {
20.                         mayNoB = Math.max(mayNoB - 1, -1);
21.                         hasB = mayNoB;
22.                     }
23.                     ans = Math.max(ans, hasB);
24.                 }
25.             }
26.         }
27.         return ans;
28.     }
29. }

复制代码

Go

1. /*
2. * @Author: LetMeFly
3. * @Date: 2025-03-16 11:14:38
4. * @LastEditors: LetMeFly.xyz
5. * @LastEditTime: 2025-03-16 11:18:01
6. */
7. package main
9. func largestVariance(s string) (ans int) {
10.     for i := byte(0); i < 26; i++ {
11.         a := i + 'a'
12.         for j := byte(0); j < 26; j++ {
13.             b := j + 'a'
14.             mayNoB, hasB := 0, -10000000
15.             for _, c := range s {
16.                 if byte(c) == a {
17.                     mayNoB = max(mayNoB + 1, 1)
18.                     hasB++
19.                 } else if byte(c) == b {
20.                     mayNoB = max(mayNoB - 1, -1)
21.                     hasB = mayNoB
22.                 }
23.                 ans = max(ans, hasB)
24.             }
25.         }
26.     }
27.     return
28. }

复制代码

  同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~
  千篇源码题解已开源

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。