LeetCode Note Java 00424：Longest Repeating Character Replacement

給定 k 次替換字母機會，回傳字串 s 經過替換後可形成的最長重複字母字串的長度。

題目

Longest Repeating Character Replacement Medium

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

解法

列出想法：

• 題目換句話說：一定範圍內，非重複最多次的字母數量小於等於 k
• 判斷新範圍合不合理的方法
• 雙指針走完一條 String
• 指針前進條件：
• 左指針：不符合維持範圍條件，所以前進左指針
• 右指針：符合維持範圍條件，所以前進右指針

class Solution {
    public int characterReplacement(String s, int k) {
        int[] arr = new int[26];
        int ans = 0;
        int max = 0; // 範圍內重複最多的字的次數
        int i = 0; // i 左邊界
        for (int j = 0; j < s.length(); j++) { // j 右邊界
            arr[s.charAt(j) - 'A']++;
            max = Math.max(max, arr[s.charAt(j) - 'A']);
            if (j - i + 1 - max > k) {
                arr[s.charAt(i) - 'A']--;
                i++;
            }
            ans = Math.max(ans, j - i + 1);
        }
        return ans;
    }
}

參考資料

leetcode/java/0424-longest-repeating-character-replacement.java

【LeetCode】424. 替换后的最长重复字符 Longest Repeating Character Replacement（Python）