golang刷leetcode：最大波动的子字符串

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

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

解题思路：

1，问题简化：首先我们总是可以拆分出长度为1的子串，最小波动值必为1；因此本题就是求最大波动值

2，假设我们已经知道i位置之前的包含b的子串波动值f0(i-1,a,b)，不包含b的子串波动值f1(i,a,b),其中a为出现频率最大的字符，b为出现频率最小的字符

3，对于i位置有三种情况：

A，s[i]==a

B，s[i]==b

C，是其他字符

4，对于情况B，又分两种情况需要考虑

B1，前i-1个字符中含有b

B2，前i-1个字符中不含b

5，递推方程如下

A，s[i]==a

f0(i,a,b)=f0(i-1,a,b)+1

f1(i,a,b)=f1(i-1,a,b)+1

B，s[i]==b

f0(i,a,b)=max(f0(i-1,a,b)-1,-1)

f1(i,a,b)=max(f1(i-1,a,b)-1,f0(i-1,a,b)-1,-1)

C，是其他字符

f0(i,a,b)=f0(i-1,a,b)

f1(i,a,b)=f1(i-1,a,b)

6,由于只依赖i-1位置，所以两个变量即可

代码实现

func largestVariance(s string) int {
    res:=0
    for a:='a';a<='z';a++{
        for b:='a';b<='z';b++{
            if a==b{
                continue
            }
           for  i,dp0,dp1:= 0,-10000,-10000; i < len(s);i++ {
               v:=0
               if s[i] == byte(a){
                   v=1
               }
               if s[i]==byte(b){
                   v=-1
               }
              if s[i]==byte(b){
               dp1=max(dp1 + v, max(dp0 + v, v))
               }else{
                 dp1 = dp1 + v
               }
                dp0 = max(dp0 + v, v)             
                res = max(res, dp1) 
               }
          }        
    }
    return res
}

func max(a,b int)int{
    if a>b{
        return a
    }
    return b
}

复制