Modified the sliding window template, short Java


  • 0
    M

    The sliding window template I referred the below post. It really can solve most sliding windows problems
    https://discuss.leetcode.com/topic/30941/here-is-a-10-line-template-that-can-solve-most-substring-problems

    This problem is also similar to "Longest substring with at most K distinct characters". So

    length of substring - the number of maximum occuring character in substring <= k
    
    public int characterReplacement(String s, int k) {
            // length of substring - the number of maximum occuring character in substring <= k
            if (s.length() < k) return s.length();
            int left = 0, right = 0;
            int[] hash = new int[256];
            int maxOccur = 0;
            int maxLen = 0;
            while (right < s.length()) {
                if (hash[s.charAt(right++)]++ == 0) count++;
                maxOccur = Math.max(maxOccur, hash[s.charAt(right - 1)]);
                if (right - left - maxOccur <= k) {
                    maxLen = Math.max(maxLen, right - left);
                }
                if (right - left - maxOccur > k && hash[s.charAt(left++)]-- == 1) count--;
            }
            return maxLen;
        }
    

    The above code is from the sliding window template, the count is obviously useless, so remove it

    public int characterReplacement(String s, int k) {
            // length of substring - the number of maximum occuring character in substring <= k
            if (s.length() < k) return s.length();
            int left = 0, right = 0;
            int[] hash = new int[256];
            int maxOccur = 0;
            int maxLen = 0;
            
            while (right < s.length()) {
                hash[s.charAt(right)]++;
                maxOccur = Math.max(maxOccur, hash[s.charAt(right)]);
                right++;
                if (right - left - maxOccur <= k) {
                    maxLen = Math.max(maxLen, right - left);
                }
                if (right - left - maxOccur > k) hash[s.charAt(left++)]--;
            }
            return maxLen;
        }
    

  • 0
    I

    How did you know to use the sliding window here? I could not even think of this and I feel so stupid after seeing so many discuss solutions using sliding window...


  • 0
    M

    Because the finding process is like a window which can be extended and also be shrinked.


Log in to reply
 

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