424. Longest Repeating Character Replacement 发表于 2022-05-04 Sliding Window1234567891011121314151617181920212223242526272829303132class Solution { public int characterReplacement(String s, int k) { // window: [i, j] int[] windowMap = new int[26]; int maxLength = 0; int i = 0; for (int j = 0; j < s.length(); j++) { windowMap[s.charAt(j) - 'A']++; // 移除元素直到 window 满足条件 while (windowIllegal(windowMap, k)) { windowMap[s.charAt(i) - 'A']--; i++; } maxLength = Math.max(maxLength, j - i + 1); } return maxLength; } private boolean windowIllegal(int[] windowMap, int k) { int charCount = 0, mostCharCount = 0; for (int count : windowMap) { charCount += count; mostCharCount = Math.max(mostCharCount, count); } return charCount - mostCharCount > k; }} Sliding Window1234567891011121314151617181920212223class Solution { public int characterReplacement(String s, int k) { // window: [i, j] int[] windowMap = new int[26]; int mostCharCount = 0, maxLength = 0; int i = 0; for (int j = 0; j < s.length(); j++) { windowMap[s.charAt(j) - 'A']++; mostCharCount = Math.max(mostCharCount, windowMap[s.charAt(j) - 'A']); if (j - i + 1 > mostCharCount + k) { windowMap[s.charAt(i) - 'A']--; i++; } maxLength = Math.max(maxLength, j - i + 1); } return maxLength; }} Reference424. Longest Repeating Character Replacement