424. Longest Repeating Character Replacement

Link

Solution

感覺上是透過left, right 指定一個range。並想方法判斷range是否符合期待 (a.k.a 能夠轉換成連續字串)。

另外要設定left, right增加跟減少的condition。

例如當原本的range不符合期待，就將left減少。

mostFreq在某些狀況可能是無效的，例如 AAAABBC, k = 1

當進行到AAABB時會移動left, 使之變成AABB,照理說mostFreq應該變成2, 然而按程式邏輯還是3

但這個不重要，至少mostFreq是3的case的確生效過，在生效時也確實update了maxLength ,

我們目的是要最長符合條件的substring, 之後的不正確的mostFreq並不會影響判斷結果。

在之後的case, 只有left前進時觸發mostFreq更新 (意味著有新的character超過舊的maxFreq)才要判斷是否有機會更新maxLengh;

 public int characterReplacement(String s, int k) {
        int[] count = new int[26];
        int max = 0;
        int needToBeChanged = 0, mostFrequent = 0, left = 0;
        for(int right = 0; right < s.length(); right++ ){
            count[s.charAt(right) - 'A']++;
            mostFrequent = Math.max(mostFrequent, count[s.charAt(right) - 'A']);
            
            needToBeChanged = (right - left + 1) - mostFrequent;
            while(needToBeChanged > k){
                count[s.charAt(left)-'A']--;
                left++;
                needToBeChanged = (right - left + 1) - mostFrequent;
            }
            
            max = Math.max(max, right-left+1);
        }
        return max;
    }