2272. Substring With Largest Variance[MaxSubarraySum]

https://leetcode.com/problems/substring-with-largest-variance/
算是很巧妙的转换了，没想出来。同时也有更有趣的解法，记下来备忘。

题目分析

乍一看是一道普通的dp题目，但构造不出来。
其实题目中的小写字母，完全可以遍历枚举，于是问题可以进行转化：转化成只有两个字母参与的子串。
统计两个字母组成的字符串，其中差异最大的子串，就是一个经典的MaxSubarraySum问题，也叫Kadane算法，这里就不多说了。

不过，问题并没有解决，题目中还有限制条件，不能只包含最多的那个字母，另一个字母至少出现一次，所以需要做一些变化，一个很直观的变化就是，用一个flag表示有没有出现，如果出现了，那就是正常的MaxSubarraySum，如果没有，那最终的结果需要-1。
这样的解法如下：

class Solution:
    def largestVariance(self, s: str) -> int:
        st = set(s)
        res = 0
        for x in st:
            for y in st:
                if x != y:
                    hasY = False
                    acc = 0
                    for c in s:
                        if c != x and c != y:
                            continue
                        if c == x:
                            acc += 1
                            if hasY:
                                res = max(res, acc)
                            else:
                                res = max(res, acc - 1)
                        elif c == y:
                            if acc > 0:
                                hasY = True
                                acc -= 1
                            else:
                                hasY = False
                                acc = 0
        return res

还有一个相反的策略，不够直观，但也挺巧妙的，维护左侧累计的最小值，最大值就是 当前累计-左侧最小累计。
里边的一个小trick是，默认上一个左侧累计是0，左侧最小累计初始是inf，只有在遇到y时才更新左侧最小累计，完美解决了只要需要一个y的问题。

class Solution:
    def largestVariance(self, s: str) -> int:
        st = set(s)
        res = 0
        for x in st:
            for y in st:
                if x != y:
                    acc = 0
                    prevDeletedPart = 0
                    deletedPart = 10**5
                    for c in s:
                        if c != x and c != y:
                            continue
                        if c == x:
                            acc += 1
                        elif c == y:
                            deletedPart = min(deletedPart, prevDeletedPart)
                            acc -= 1
                            prevDeletedPart = acc
                        res = max(res, acc - deletedPart)
        return res