Java Sliding Window Easy to Understand


  • 7
    S

    The problem is similar to longest substring with most K distinct characte. But this time, the constraint is we can only have most K characters that is different with the most frequent character in the substring. For example in the sliding window:

    "ABBBAC" most frequent character is B with count 3, all other character is count as different to B, 
        which is A and C, and the result is 2 + 1 = 3. 
    

    Each time we count the different characters. If it is not bigger than k we extend the sliding window.
    Since we only have 26 characters, keep the count in a integer array is good enough.
    Complete code:

    public class Solution {
        public int characterReplacement(String s, int k) {
            if(s == null || s.length() == 0){
                return 0;
            }
            int max = 0;
            int[] ch = new int[26];
            char[] str = s.toCharArray();
            for(int i=0, j=0; i<s.length(); i++){
                while(j < s.length()){
                    ch[str[j] - 'A']++;
                    if(count(ch) > k){  //If exceed k, break
                        ch[str[j] - 'A']--;
                        break;
                    }
                    j++;
                }
                max = Math.max(max, j-i);
                ch[str[i] - 'A']--;
            }
            return max;
        }
        //Count the number of character that is different to the longest character
        public int count(int[] ch){
            int max = 0;
            int sum = 0;
            for(int val:ch){
                sum += val;
                max = Math.max(max, val);
            }
            return sum - max;
        }
    }
    

  • 1
    Y

    @star1993 easy understanding.


  • 0
    S

    @yuhengw Thanks, hope it helps~


  • 1

    Nice solution and very easy to understand.
    But I still have some hard time following the inner for loop, I have put some verbose code below to make it easier to understand how the sliding window works.

    // this makes it truly sliding, both i and j increases until cannot slide any more
    for(int i=0, j=0; i<s.length() && j<s.length(); i++, j++){ 
        while(j < s.length()){
            ch[str[j] - 'A']++;
            if(count(ch) > k){  //If exceed k, break
                ch[str[j] - 'A']--;
                break;
            }
            j++;
        }
        j--; // recover window back to normal
        max = Math.max(max, j-i+1);
        ch[str[i] - 'A']--;
    }

Log in to reply
 

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