LeetCode 2272. Substring With Largest Variance

May 15, 2022

雙周賽78。有點像是kadane的變形版，難度算高，比賽當時還真沒想到是dp。

題目

字串的變異值指的是字串中出現的任意2字元出現次數的最大差值。兩個字元可能相同也可能不同。
輸入小寫字串s，回傳s所有子字串中的最大變異值。

解法

又是霸凌python的一天，同樣的演算法，python會超時，java卻勝過100%提交。難怪都說至少要學兩種語言。

題目說在某子字串中，找兩個字元出現次數的最大差值，而且兩個字元可以相同。
但是相同的話差值一定是0，所以只要找枚舉25*26種字元組合就可以。

枚舉不同的字元a和b，各遍歷一次字串s，如果碰到a則+1，碰到b則-1，問題就簡化成最大子陣列了。
維護變數score代表最大子陣列的和，初始為0。
變數v代表實際的變異值，但因為至少要有一個字元b，所以變異值要先初始化為-inf，在第一個b出現之後才以score去更新。

遍歷s中的字元c，當a出現時，子陣列和+1，變異值也+1。
當b出現時，有兩種可能：

使用新的子陣列，加上當前的b，變異值=子陣列和-1
沿用原本的變異值，變異值-1

因為子陣列已經合併到最大的變異值裡面去了，所以要將子陣列和歸0。

class Solution {
    public int largestVariance(String s) {
        char[] cs=s.toCharArray();
        int ans=0;
        for(int i=97;i<123;i++){
            for(int j=97;j<123;j++){
                if(i==j)continue;
                char a=(char)i;
                char b=(char)j;
                int score=0;
                int v=-1000000000;
                for(char c:cs){
                    if(c==a){
                        score++;
                        v++;
                    }else if(c==b){
                        v=Math.max(score-1,v-1);
                        score=0;
                    }
                    if(v>ans)ans=v;
                }
            }
        }
        return ans;
    }
}

如果先遍歷一次s，找到有出現過的字元集合cs，只遍歷cs裡面的字元，就能勉強通過了。
值得注意的是，如果用max函數更新ans，時間會大幅上升，所以要用if減少賦值次數。

class Solution:
    def largestVariance(self, s: str) -> int:
        ans=0
        cs=set(s)
        for a in cs:
            for b in cs:
                if a==b:
                    continue
                score=0
                v=-math.inf
                for c in s:
                    if c==a:
                        score+=1
                        v+=1
                    elif c==b:
                        v=max(score,v)-1
                        score=0                
                    if v>ans:
                        ans=v
                    
        return ans

mocowcow

題目

解法