424. Longest Repeating Character Replacement - Medium

前往題目

思路

關鍵是window長度減掉該window下最多字母的數量，剩下的字母就是必須替換的，所以最多只能k個

1. Sliding window，檢查每個字母，紀錄出現次數
2. 當window的長度減掉最多count的字母，大於k的時候就超出規範了，因此要移動左指針
3. 每次循環都更新一次最大長度，也就是window的長度

Code

class Solution {
    public int characterReplacement(String s, int k) {
        int res = 0;
        HashMap<Character, Integer> map = new HashMap();

        int l = 0; // Left pointer

        map.put(s.charAt(l), 1);

        for (int r = 1; r < s.length(); ++r) {
            // Count the alphabets
            map.put(s.charAt(r), 1 + map.getOrDefault(s.charAt(r), 0));

            // Max count
            int maxCount = -1;

            // Find the maxCount
            for (int count : map.values()) {
                maxCount = Math.max(maxCount, count);
            }
            
            // Exceeded the k
            if (((r - l + 1) - maxCount) > k) {
                // Decrease the count
                map.put(s.charAt(l), map.get(s.charAt(l)) - 1);
                l += 1; // Move the left pointer (Move the window)
            }
            res = Math.max(res, r - l + 1);
        }

        return res;
    }
}

2024/02/02

• 沒寫出來，寫了前置題1004與2024
• 其實這題也可以用前置題的方法，直接疊代26次就好，每次都取一個字母為基準，這樣時間也只有O(26N)非常划算
• 以下方法和上面的方法一樣，只是使用array而不是hashmap，其實這題用array更好，因為一定知道index

// T: O(26N)
// S: O(1)
class Solution {
    public int characterReplacement(String s, int k) {
        int i = 0, res = 0;
        // Counts of the alphabets
        int[] count = new int[26];
        // 固定j，左指針i移動
        for (int j = 0; j < s.length(); ++j) {
            // 循環開始時會多一位，所以加上1
            count[s.charAt(j) - 'A'] += 1;
            // 判斷當前的區間減去count陣列裡最大值是否大於k
            // 大於k就代表當前需替換字母個數已超出k
            while ((j - i + 1 - maxVal(count)) > k) {
                // 退掉i
                count[s.charAt(i) - 'A'] -= 1;
                // 右移左指針
                ++i;
            }
            res = Math.max(res, j - i + 1);
        }
        return res;
    }

    // 找最大值
    private int maxVal(int[] count) {
        int max = 0;

        for (int num : count) {
            max = Math.max(max, num);
        }

        return max;
    }
}

2024/05/01

• 看了思路才想起來怎麼解🤣