Sliding Window - Java - Easy Explanation - 15 lines


  • 5
    A
    /*
        The whole idea is that if we have a string of length N out of which M characters are same,
        we can replace (N - M) characters to get a continueous string of N characters. 
        If M <= K. N is the local maximum for this window.
        If this length is greater than K. Slide the window.
        */
        public int characterReplacement(String s, int k) {
            int[] charCount = new int[26];
            
            int left, right, maxCount, maxLen;
            left = right = maxCount = maxLen = 0;
        
            while(right < s.length()){
                charCount[s.charAt(right) - 'A']++;
                maxCount = Math.max(maxCount, charCount[s.charAt(right) - 'A']);
                if(right - left + 1 - maxCount > k) charCount[s.charAt(left++) - 'A']--;
                maxLen = Math.max(right++ - left + 1, maxLen);
            }
            return maxLen;
        }
    

  • 3
    G

    Nice post. Similar as my solution. Its not necessary to find the maximum count of the 26 characters in each move. We only need to record the maxCount. Because we can get a larger length only if there is a larger character count.


  • 0
    D

    This is just so beautiful! Awesome reasoning about why we just need one max @ghanpipi-gmail-com !


  • 0
    D

    @ghanpipi-gmail-com Actually, I have a question. Will this line

    if(right - left + 1 - maxCount > k) charCount[s.charAt(left++) - 'A']--;
    

    still be correct even if maxCount is more than what it should be? If that's the case, we'll subtract a larger quantity from the LHS and then the chance of it being > k will be reduced and then we won't subtract the char count for left.


Log in to reply
 

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