玛卡巴卡的卡巴卡玛 发表于 2025-4-2 22:51:51

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

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

力扣题目链接:https://leetcode.cn/problems/substring-with-largest-variance/
字符串的 波动 定义为子字符串中出现次数 最多 的字符次数与出现次数 最少 的字符次数之差。
给你一个字符串 s ,它只包含小写英文字母。请你返回 s 里所有 子字符串的 最大波动 值。
子字符串 是一个字符串的一段一连字符序列。
 
示例 1:
<b>输入:</b>s = "aababbb"
<b>输出:</b>3
<strong>解释:</strong>
所有可能的波动值和它们对应的子字符串如以下所示:
- 波动值为 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:
<b>输入:</b>s = "abcde"
<b>输出:</b>0
<strong>解释:</strong>
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++

/*
* @Author: LetMeFly
* @Date: 2025-03-16 10:43:25
* @LastEditors: LetMeFly.xyz
* @LastEditTime: 2025-03-16 11:03:26
*/
#ifdef _WIN32
#include "_toVector.h"
#endif

#ifdef FirstTry// WA - 例如baa,一个变量会导致不选b,而只有aa虽然cnt比较大但不一定最优
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) {
                        // cnt = max(cnt - 1, 0);
                        if (cnt - 1 >= 0) {
                            cnt--;
                            hasB = true;
                        } else {
                            cnt = 0;
                            hasB = false;
                        }
                  }
                  if (hasB) {
                        ans = max(ans, cnt);
                  }
                }
                // printf("a = %c, b = %c, ans = %d\n", a, b, ans);
            }
      }
      return ans;
    }
};
#else// FirstTry
// SecondTry
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// FirstTry
Python

'''
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

/*
* @Author: LetMeFly
* @Date: 2025-03-16 11:09:39
* @LastEditors: LetMeFly.xyz
* @LastEditTime: 2025-03-16 11:13:27
*/
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

/*
* @Author: LetMeFly
* @Date: 2025-03-16 11:14:38
* @LastEditors: LetMeFly.xyz
* @LastEditTime: 2025-03-16 11:18:01
*/
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和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~
千篇源码题解已开源

免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!更多信息从访问主页:qidao123.com:ToB企服之家,中国第一个企服评测及商务社交产业平台。
页: [1]
查看完整版本: LeetCode 2272.最大波动的子字符串:转为多次的最大子数组和 - 一步步思考推导