slidingwindow

• Helps us avoid duplicating work when dealing with contigous elements (subarrays, etc)
• end - start + 1 is our window size

Fixed size window

start = end = 0
while(end < arraylength){
  // include window end
  if(window is valid){
    // perform calculations
    // move window start appropriately
  }
}

2379. Minimum Recolors to Get K Consecutive Black Blocks

Input: blocks = "WBBWWBBWBW", k = 7
Output: 3
Explanation:
One way to achieve 7 consecutive black blocks is to recolor the 0th, 3rd, and 4th blocks
so that blocks = "BBBBBBBWBW". 
It can be shown that there is no way to achieve 7 consecutive black blocks in less than 3 operations.
Therefore, we return 3.

public int minimumRecolors(String blocks, int k) {
        int count = 0, min = Integer.MAX_VALUE, i = 0;

        for(int j = 0; j < blocks.length(); j++){
            if(blocks.charAt(j) == 'W') count++;
            
            // valid window
            if(j - i + 1 == k){ 
                min = Math.min(min, count);
                if(blocks.charAt(i++) == 'W') count--;
            }
        }
        return min;
    }

1343. Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold

Given an array of integers arr and two integers k and threshold, return the number of sub-arrays of size k and average greater than or equal to threshold.

Input: arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4
Output: 3
Explanation: Sub-arrays [2,5,5],[5,5,5] and [5,5,8] have averages 4, 5 and 6 respectively.
All other sub-arrays of size 3 have averages less than 4 (the threshold).

public int numOfSubarrays(int[] arr, int k, int threshold) {
        int sum = 0, count = 0, m = threshold * k;

        for(int i = 0; i < arr.length; i++){
            sum += arr[i]; // expand window
            // do calculations if window size has reached K
            if(i + 1 >= k){
                if(sum >= m) count++;
                sum -= arr[i - k + 1];
            }
        }
        return count;
    }

Dynamic size window

start = end = 0
while(end < arraylength){
  // include window end

  // window shrink
  // we can choose to shrink the window multiple times or ONCE
  while or IF(can shrink){ 
    // perform calculations
    // move window start appropriately
  }
}

Caterpillar-style movement

• We can shrink window one or more times based on some conditions while end is stationery

1004. Max Consecutive Ones III

Given a binary array nums and an integer k, return the maximum number of consecutive 1's in the array if you can flip at most k 0's.

Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6
Explanation: [1,1,1,0,0,1,1,1,1,1,1]

class Solution {
    public int longestOnes(int[] nums, int k) {
        // make note of zeros
        // if zeros > k, shrink window once
        // we can replace the WHILE condition to shrink window with IF, 
        // and it works just fine
        int i = 0, zeros = 0, ans = -1;
        for(int j = 0; j < nums.length; j++){
            zeros += (nums[j] ^ 1);

            if(zeros > k) zeros -= (nums[i++] ^ 1);

            ans = Math.max(ans, j - i + 1);
        }
        return ans;
    }
}

76. Minimum Window Substring (Hard)

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

• Create a variable matches that count how many of the chars in string t is in our window
• window = BBACB , t = ABC
• matches = 3 as extra freqs are not counted in matches (but freqs are still noted elsewhere for later use)

public String minWindow(String s, String t) {
    int m = s.length(), n = t.length();

    int[] tfreq = new int[128];
    for (int i = 0; i < n; i++) ++tfreq[t.charAt(i)];

    int[] window = new int[128];
    int matches = 0, min = Integer.MAX_VALUE, i = 0, ans = 0;

    for (int j = 0; j < m; j++) {
        // increase matches only if window has freq atmost equal to freq in t
        char rightChar = s.charAt(j);
        if (++window[rightChar] <= tfreq[rightChar]) 
            ++matches;

        // Shrink window
        while (matches == n) {
            if (j - i + 1 < min) {
                min = j - i + 1;
                ans = i;
            }
            // reduce matches if moving i causes our window to not have t
            // stops shrinking as window doesn't contain t now
            char leftChar = s.charAt(i++);
            if (--window[leftChar] < tfreq[leftChar]) 
                --matches; 
        }
    }
    return min == Integer.MAX_VALUE ? "" : s.substring(ans, ans + min);
}

Starting a new window (or Resetting count)

• This is useful for when we want to track longest consecutive-style problems
  • Incresae count if sequence is continued
  • Reset if sequence is broken

485. Max Consecutive Ones

Given a binary array nums, return the maximum number of consecutive 1's in the array.

Input: nums = [1,1,0,1,1,1]
Output: 3
Explanation: The first two digits or the last three digits are consecutive 1s.
The maximum number of consecutive 1s is 3.

public int findMaxConsecutiveOnes(int[] nums) {
    int max = 0, count = 0;
    for(int i: nums){
        if(i == 0) count = 0; // reset count
        else max = Math.max(max, ++count);
    }
    return max;
}

2414. Length of the Longest Alphabetical Continuous Substring

Input: s = "abacaba"
Output: 2
Explanation: There are 4 distinct continuous substrings: "a", "b", "c" and "ab".
"ab" is the longest continuous substring.

public int longestContinuousSubstring(String s) {
    int count = 1, max = 1, prev = s.charAt(0);
    for(int i = 1; i < s.length(); i++){
        
        // increase count if curr char is prev + 1
        char c = s.charAt(i);
        
        if(prev + 1 == c) max = Math.max(max, ++count);
        else count = 1;

        prev = c;
    }
    return max;
}