Pattern - 1:Sliding Window

This pattern is used when any problem statement has something like calculate(sum , avg, max, math,duplicate) with in subarray,sublist and substring (widow).

Technique: 

• Keep Increasing the window if the computed value is less than the given  criteria.
• Print the computed value if criteria is exactly met.
• keep Decreasing  the window   if the computed value is more than the given criteria.                                          

General snippet of Code:

int slidingWindowPattern(int[] nums , int k){

    int windowStart  = 0;
    int ComputeValue = 0;

    for(int windowEnd = 0; windowEnd < nums.length; windowEnd++){

        int endValue = nums[windowEnd];
        ComputeValue += endValue;// Keep adding the value

        if(windowEnd > k){
            int startValue = nums[windowStart];
            ComputeValue -= startValue;
        }
    }
    return ComputeValue;
}

Example 1 - Easy:

Given an input array nums , find the sum of all subarray of size k.

Input:
nums = [1, 2, 3, 4, 5, 6, 7] k = 3
Output:
result = [6, 9, 12, 15, 18]

Explanation:

First Window : 1 + 2 + 3 = 6 

Second Window : 2 + 3 + 4 = 9

Third Window : 3 + 4 + 5 = 12

Fourth Window : 4 + 5 + 6 = 15

Fifth Window : 5 + 6 + 7 = 18

Solution :

As discussed above , 

• keep increasing the window until the size of the window is less than K by storing the summation of all elements into a computed sum variable  . 
• If the window size is equal to K then we store into result array .
• If the window is greater than K then we shrink the window by removing the starting window element from the summation variable.

int[] findSumOfSubArrayOfSizeK(int[] nums, int k){

    int[] result = new int[nums.length - (k - 1)];
    int windowStart  = 0;
    int ComputeSum = 0;

    for(int windowEnd = 0; windowEnd < nums.length; windowEnd++){

        int endValue = nums[windowEnd];
        ComputeSum += endValue;// Keep Increasing the window if the computed value is less than the given  criteria

        if(windowEnd >= k - 1){
            int startValue = nums[windowStart];
            result[windowStart++] = ComputeSum; //Add the computed sum if criteria is met.
            ComputeSum -= startValue;//keep Decreasing  the window   if the computed value is more than the given criteria.  
        }
    }
    return result;
}

Followup:

1. Can you find maximum element for all subarray of size k ?
2. Can you find minimum element for all subarray of size k ?
3. Can you find average for all subarray of size k ?

Example 2 - Medium :

Given a String ,find the longest substring with k unique characters in given string .

Input:
Str = "aabbcc", k = 2
Output:
result = 4 ("aabb"  or  "bbcc")

Solution: In the above problem the criteria is to check the widow size(No of elements in the window) is equal to K or not . In this problem , the criteria is to check the no of unique characters in the widow is equal to K or not.So, we can not simply keep adding elements in the window and check the criteria .we need to use some data structure to identify how many unique characters are present when each element is being added to the window .Hash table is the right data structure to identify the no of occurrences of each character .

• Keep Increasing the widow until no of unique characters present in the map is less than "K".
• Add it to the result if it is longest string among all possible substrings when the map size is equal to "K".
• Keep decreasing the window until no of unique characters present in the map is more than "K".

Solution :

 int findLongestSubstringWithKuniqueChar(String str, int k){

    int result = Integer.MIN_VALUE;
    int windowStart  = 0;
    Map<Character, Integer> ComputeMap = new HashMap<>();

    for(int windowEnd = 0; windowEnd < str.length(); windowEnd++){

        char endChar = str.charAt(windowEnd);
        ComputeMap.put(endChar, ComputeMap.getOrDefault(endChar, 0) + 1);

        if(ComputeMap.size() > k){
            char startValue = str.charAt(windowStart++);
            ComputeMap.put(startValue, ComputeMap.getOrDefault(startValue, 0) - 1);
            if(ComputeMap.get(startValue) == 0){
                ComputeMap.remove(startValue);
            }
        }
        result = Math.max(result, windowEnd - windowStart + 1 );
    }
    return result;
}

References:

Geeks For Geeks:find the longest substring with k unique characters in a given string

LeetCode:find the longest substring with k unique characters in given string

April 03, 2021 Tags : #slidingwindow , sliding window technique

Subscribe by Email

Follow Updates Articles from This Blog via Email