Leetcode 2272. Substring With Largest Variance [Python]

改版的Kadane算法，原有的kadane算法是dp[i] = max(dp[i-1], 0) + arr[i]。这里a,b的两个字分别统计数量，也就是类似1和-1，当counta >countb, 且b已经在当前的substring里了，就可以计算res = max（res，counta - countb）。而如果counta 已经 < countb，且依然还有 letter b还没遍历到，则此时的counta - countb已经无意义，counta 和countb改回0.这里之所以要看是否还有剩余的letter b，可以看一个例子“lirpaa” 此时如果‘a’ = a，‘b’ = l，不要remainb > 0条件的话，上来counta（0） < countb（1），但是其实此时的countb应该保留，不过由于没有remainb > 0条件，counta 和countb都会变为0. 导致counta - countb的操作没法做。

class Solution:
    def largestVariance(self, s: str) -> int:
        count = collections.Counter(s)
        res = float('-inf')
        if all(count[c] == 1 for c in count.keys()) or len(count.keys()) == 1:return 0
        for a,b in permutations(count, 2):
            counta = 0
            countb = 0
            remainb = count[b]
            for i,l in enumerate(s):
                if l not in {a,b}:continue
                if a == l:
                    counta += 1
                elif b == l:
                    countb += 1
                    remainb -= 1
                if counta < countb and remainb > 0:
                    counta = countb = 0
                if countb > 0:
                    res = max(res, counta - countb)
        return res

记录一种错误写法，这种写法会导致的问题就是substring里只有一种字母。

class Solution:
    def largestVariance(self, s: str) -> int:
        count = collections.Counter(s)
        if len(count.keys()) == 1 or all(count[c] == 1 for c in count.keys()):
            return 0
        ans = float('-inf')
        def kadane(arr):
            dp = [0]*len(arr)
            for i in range(1,len(arr)):
                dp[i] = max(dp[i-1],0) + arr[i]
            return max(dp)
        
        print(permutations(set(s),2))
        
        for l1,l2 in permutations(set(s),2):
            arr1 = []
            arr2 = []
            for i,c in enumerate(s):
                if l1 == c:
                    arr1.append(1)
                    arr2.append(-1)
                elif l2 == c:
                    arr1.append(-1)
                    arr2.append(1)
            ans = max([ans, kadane(arr1), kadane(arr2)])
        return ans