Java Sliding Window, 12 lines with explanation.

  • 0
    public class Solution {
        public int characterReplacement(String s, int k) {
            int[] map = new int[26];
            char[] sc = s.toCharArray();
            int l = 0, r= 0,maxLen = 0,result = 0;
            while (r < sc.length) {
                maxLen = Math.max(maxLen, ++map[sc[r++]-'A']);
                while (r - l - maxLen>k) map[sc[l++]-'A']--;
                result = Math.max(result, r - l);
            return result;

    I use a map to store every character's frequency in the window. And calculate the max frequency as maxLen, so the other characters in the window can be replaced if r-l-maxLen<=k. Otherwise, shrink the window and update map while the window is valid again. Finally calculate and update the max valid window's length.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.