Sliding Window Strategies Flashcards
Maximum Sum Subarray of Size K
Given an array of positive numbers and a positive number ‘k’, find the maximum sum of any contiguous subarray of size ‘k’.
Example 1
Input: [2, 1, 5, 1, 3, 2], k=3
Output: 9
Explanation: Subarray with maximum sum is [5, 1, 3].
Example 2
Input: [2, 3, 4, 1, 5], k=2
Output: 7
Explanation: Subarray with maximum sum is [3, 4].
If you observe closely, you will realize that to calculate the sum of a contiguous subarray we can utilize the sum of the previous subarray. For this, consider each subarray as a Sliding Window of size ‘k’. To calculate the sum of the next subarray, we need to slide the window ahead by one element. So to slide the window forward and calculate the sum of the new position of the sliding window, we need to do two things:
- Subtract the element going out of the sliding window i.e., subtract the first element of the window.
- Add the new element getting included in the sliding window i.e., the element coming right after the end of the window.
This approach will save us from re-calculating the sum of the overlapping part of the sliding window.
The time complexity of the above algorithm will be O(N).
The algorithm runs in constant space O(1).
Smallest Subarray with a given sum
Given an array of positive numbers and a positive number ‘S’, find the length of the smallest contiguous subarray whose sum is greater than or equal to ‘S’. Return 0, if no such subarray exists.
Example 1
Input: [2, 1, 5, 2, 3, 2], S=7
Output: 2
Explanation: The smallest subarray with a sum great than or equal to ‘7’ is [5, 2].
Example 2
Input: [2, 1, 5, 2, 8], S=7
Output: 1
Explanation: The smallest subarray with a sum greater than or equal to ‘7’ is [8].
Example 3
Input: [3, 4, 1, 1, 6], S=8
Output: 3
Explanation: Smallest subarrays with a sum greater than or equal to ‘8’ are [3, 4, 1] or [1, 1, 6].
This problem follows the Sliding Window pattern and we can use a similar strategy as discussed in Maximum Sum Subarray of Size K. There is one difference though: in this problem, the size of the sliding window is not fixed. Here is how we will solve this problem:
- First, we will add-up elements from the beginning of the array until their sum becomes greater than or equal to ‘S’.
- These elements will constitute our sliding window. We are asked to find the smallest such window having a sum greater than or equal to ‘S’. We will remember the length of this window as the smallest window so far.
- After this, we will keep adding one element in the sliding window (i.e. slide the window ahead), in a stepwise fashion.
- In each step, we will also try to shrink the window from the beginning. We will shrink the window until the window’s sum is smaller than ‘S’ again. This is needed as we intend to find the smallest window. This shrinking will also happen in multiple steps; in each step we will do two things:
- Check if the current window length is the smallest so far, and if so, remember its length.
- Subtract the first element of the window from the running sum to shrink the sliding window.
The time complexity of the above algorithm will be O(N). The outer for loop runs for all elements and the inner while loop processes each element only once, therefore the time complexity of the algorithm will be O(N+N) which is asymptotically equivalent to O(N).
The algorithm runs in constant space O(1).
Longest Substring with K Distinct Characters
Given a string, find the length of the longest substring in it with no more than K distinct characters.
Example 1
Input: String=”araaci”, K=2
Output: 4
Explanation: The longest substring with no more than ‘2’ distinct characters is “araa”.
Example 2
Input: String=”araaci”, K=1
Output: 2
Explanation: The longest substring with no more than ‘1’ distinct characters is “aa”.
Example 3
Input: String=”cbbebi”, K=3
Output: 5
Explanation: The longest substrings with no more than ‘3’ distinct characters are “cbbeb” & “bbebi”.
This problem follows the Sliding Window pattern and we can use a similar dynamic sliding window strategy as discussed in Smallest Subarray with a given sum. We can use a HashMap to remember the frequency of each character we have processed. Here is how we will solve this problem:
- First, we will insert characters from the beginning of the string until we have ‘K’ distinct characters in the HashMap.
- These characters will constitute our sliding window. We are asked to find the longest such window having no more than ‘K’ distinct characters. We will remember the length of this window as the longest window so far.
- After this, we will keep adding one character in the sliding window (i.e. slide the window ahead), in a stepwise fashion.
- In each step, we will try to shrink the window from the beginning if the count of distinct characters in the HashMap is larger than ‘K’. We will shrink the window until we have no more than ‘K’ distinct characters in the HashMap. This is needed as we intend to find the longest window.
- While shrinking, we’ll decrement the frequency of the character going out of the window and remove it from the HashMap if its frequency becomes zero.
- At the end of each step, we’ll check if the current window length is the longest so far, and if so, remember its length.
The time complexity of the above algorithm will be O(N) where ‘N’ is the number of characters in the input string. The outer for loop runs for all characters and the inner while loop processes each character only once, therefore the time complexity of the algorithm will be O(N+N) which is asymptotically equivalent to O(N).
The space complexity of the algorithm is O(K), as we will be storing a maximum of ‘K+1’ characters in the HashMap.
Fruits into Baskets
Given an array of characters where each character represents a fruit tree, you are given two baskets and your goal is to put maximum number of fruits in each basket. The only restriction is that each basket can have only one type of fruit.
You can start with any tree, but once you have started you can’t skip a tree. You will pick one fruit from each tree until you cannot, i.e., you will stop when you have to pick from a third fruit type.
Write a function to return the maximum number of fruits in both the baskets.
Example 1
Input: Fruit=[‘A’, ‘B’, ‘C’, ‘A’, ‘C’]
Output: 3
Explanation: We can put 2 ‘C’ in one basket and one ‘A’ in the other from the subarray [‘C’, ‘A’, ‘C’]
Example 2
Input: Fruit=[‘A’, ‘B’, ‘C’, ‘B’, ‘B’, ‘C’]
Output: 5
Explanation: We can put 3 ‘B’ in one basket and two ‘C’ in the other basket. This can be done if we start with the second letter: [‘B’, ‘C’, ‘B’, ‘B’, ‘C’]
This problem follows the Sliding Window pattern and is quite similar to Longest Substring with K Distinct Characters. In this problem, we need to find the length of the longest subarray with no more than two distinct characters (or fruit types!). This transforms the current problem into Longest Substring with K Distinct Characters where K=2.
The time complexity of the above algorithm will be O(N) where ‘N’ is the number of characters in the input array. The outer for loop runs for all characters and the inner while loop processes each character only once, therefore the time complexity of the algorithm will be O(N+N) which is asymptotically equivalent to O(N).
The algorithm runs in constant space O(1) as there can be a maximum of three types of fruits stored in the frequency map.
No-repeat Substring
Given a string, find the length of the longest substring which has no repeating characters.
Example 1
Input: String=”aabccbb”
Output: 3
Explanation: The longest substring without any repeating characters is “abc”.
Example 2
Input: String=”abbbb”
Output: 2
Explanation: The longest substring without any repeating characters is “ab”.
Example 3
Input: String=”abccde”
Output: 3
Explanation: Longest substrings without any repeating characters are “abc” & “cde”.
This problem follows the Sliding Window pattern and we can use a similar dynamic sliding window strategy as discussed in Longest Substring with K Distinct Characters. We can use a HashMap to remember the last index of each character we have processed. Whenever we get a repeating character we will shrink our sliding window to ensure that we always have distinct characters in the sliding window.
The time complexity of the above algorithm will be O(N) where ‘N’ is the number of characters in the input string.
The space complexity of the algorithm will be O(K) where K is the number of distinct characters in the input string. This also means K<=N, because in the worst case, the whole string might not have any repeating character so the entire string will be added to the HashMap. Having said that, since we can expect a fixed set of characters in the input string (e.g., 26 for English letters), we can say that the algorithm runs in fixed space O(1); in this case, we can use a fixed-size array instead of the HashMap.
Longest Substring with Same Letters after Replacement
Given a string with lowercase letters only, if you are allowed to replace no more than ‘k’ letters with any letter, find the length of the longest substring having the same letters after replacement.
Example 1
Input: String=”aabccbb”, k=2
Output: 5
Explanation: Replace the two ‘c’ with ‘b’ to have a longest repeating substring “bbbbb”.
Example 2
Input: String=”abbcb”, k=1
Output: 4
Explanation: Replace the ‘c’ with ‘b’ to have a longest repeating substring “bbbb”.
Example 3
Input: String=”abccde”, k=1
Output: 3
Explanation: Replace the ‘b’ or ‘d’ with ‘c’ to have the longest repeating substring “ccc”.
This problem follows the Sliding Window pattern and we can use a similar dynamic sliding window strategy as discussed in No-repeat Substring. We can use a HashMap to count the frequency of each letter.
We’ll iterate through the string to add one letter at a time in the window. We’ll also keep track of the count of the maximum repeating letter in any window (let’s call it maxRepeatLetterCount). So at any time, we know that we can have a window which has one letter repeating maxRepeatLetterCount times, this means we should try to replace the remaining letters. If we have more than k remaining letters, we should shrink the window as we are not allowed to replace more than ‘k’ letters.
The time complexity of the above algorithm will be O(N) where ‘N’ is the number of letters in the input string.
As we are expecting only the lower case letters in the input string, we can conclude that the space complexity will be O(26), to store each letter’s frequency in the HashMap, which is asymptotically equal to O(1).
Longest Subarray with Ones after Replacement
Given an array containing 0s and 1s, if you are allowed to replace no more than ‘k’ 0s with 1s, find the length of the longest contiguous subarray having all 1s.
Example 1
Input: Array=[0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1], k=2
Output: 6
Explanation: Replace the ‘0’ at index 5 and 8 to have the longest contiguous subarray of 1s having length 6.
Example 2
Input: Array=[0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1], k=3
Output: 9
Explanation: Replace the ‘0’ at index 6, 9, and 10 to have the longest contiguous subarray of 1s having length 9.
This problem follows the Sliding Window pattern and is quite similar to Longest Substring with same Letters after Replacement. The only difference is that, in the problem, we only have two characters (1s and 0s) in the input arrays.
Following a similar approach, we’ll iterate through the array to add one number at a time in the window. We’ll also keep track of the maximum number of repeating 1s in the current window (let’s call it maxOnesCount). So at any time, we know that we can have a window which has 1s repeating maxOnesCount time, so we should try to replace the remaining 0s. If we have more than ‘k’ remaining 0s, we should shrink the window as we are not allowed to replace more than ‘k’ 0s.
The time complexity of the above algorithm will be O(N) where ‘N’ is the count of numbers in the input array.
The algorithm runs in constant space O(1).
Permutation in a String
Given a string and a pattern, find out if the string contains any permutation of the pattern. Permutation is defined as the re-arranging of the characters of the string. For example, “abc” has the following six permutations:
- abc
- acb
- bac
- bca
- cab
- cba
If a string has ‘n’ distinct characters it will have n! permutations.
Example 1
Input: String=”oidbcaf”, Pattern=”abc”
Output: true
Explanation: The string contains “bca” which is a permutation of the given pattern.
Example 2
Input: String=”odicf”, Pattern=”dc”
Output: false
Explanation: No permutation of the pattern is present in the given string as a substring.
Example 3
Input: String=”bcdxabcdy”, Pattern=”bcdyabcdx”
Output: true
Explanation: Both the string and the pattern are a permutation of each other.
Example 4
Input: String=”aaacb”, Pattern=”abc”
Output: true
Explanation: The string contains “acb” which is a permutation of the given pattern.
This problem follows the Sliding Window pattern and we can use a similar sliding window strategy as discussed in Longest Substring with K Distinct Characters. We can use a HashMap to remember the frequencies of all characters in the given pattern. Our goal will be to match all the characters from this HashMap with a sliding window in the given string. Here are the steps of our algorithm:
- Create a HashMap to calculate the frequencies of all characters in the pattern.
- Iterate through the string, adding one character at a time in the sliding window.
- If the character being added matches a character in the HashMap, decrement its frequency in the map. If the character frequency becomes zero, we got a complete match.
- If at any time, the number of characters matched is equal to the number of distinct characters in the pattern (i.e., total characters in the HashMap), we have gotten our required permutation.
- If the window size is greater than the length of the pattern, shrink the window to make it equal to the size of the pattern. At the same time, if the character going out was part of the pattern, put it back in the frequency HashMap.
The time complexity of the above algorithm will be O(N + M) where ‘N’ and ‘M’ are the number of characters in the input string and the pattern respectively.
The space complexity of the algorithm is O(M) since in the worst case, the whole pattern can have distinct characters which will go into the HashMap.
String Anagrams
Given a string and a pattern, find all anagrams of the pattern in the given string.
Anagram is actually a Permutation of a string. For example, “abc” has the following six anagrams:
- abc
- acb
- bac
- bca
- cab
- cba
Write a function to return a list of starting indices of the anagrams of the pattern in the given string.
Example 1
Input: String=”ppqp”, Pattern=”pq”
Output: [1, 2]
Explanation: The two anagrams of the pattern in the given string are “pq” and “qp”.
Example 2
Input: String=”abbcabc”, Pattern=”abc”
Output: [2, 3, 4]
Explanation: The three anagrams of the pattern in the given string are “bca”, “cab”, and “abc”.
This problem follows the Sliding Window pattern and is very similar to Permutation in a String. In this problem, we need to find every occurrence of any permutation of the pattern in the string. We will use a list to store the starting indices of the anagrams of the pattern in the string.
The time complexity of the above algorithm will be O(N+M) where ‘N’ and ‘M’ are the number of characters in the input string and the pattern respectively.
The space complexity of the algorithm is O(M) since in the worst case, the whole pattern can have distinct characters which will go into the HashMap. In the worst case, we also need O(N) space for the result list, this will happen when the pattern has only one character and the string contains only that character.
Smallest Window containing Substring
Given a string and a pattern, find the smallest substring in the given string which has all the characters of the given pattern.
Example 1
Input: String=”aabdec”, Pattern=”abc”
Output: “abdec”
Explanation: The smallest substring having all characters of the pattern is “abdec”
Example 2
Input: String=”abdabca”, Pattern=”abc”
Output: “abc”
Explanation: The smallest substring having all characters of the pattern is “abc”.
Example 3
Input: String=”adcad”, Pattern=”abc”
Output: “”
Explanation: No substring in the given string has all characters of the pattern.
This problem follows the Sliding Window pattern and has a lot of similarities with Permutation in a String with one difference. In this problem, we need to find a substring having all characters of the pattern which means that the required substring can have some additional characters and doesn’t need to be a permutation of the pattern. Here is how we will manage these differences:
- We will keep a running count of every matching instance of a character.
- Whenever we have matched all the characters, we will try to shrink the window from the beginning, keeping track of the smallest substring that has all the matching characters.
- We will stop the shrinking process as soon as we remove a matched character from the sliding window. One thing to note here is that we could have redundant matching characters, e.g., we might have two ‘a’ in the sliding window when we only need one ‘a’. In that case, when we encounter the first ‘a’, we will simply shrink the window without decrementing the matched count. We will decrement the matched count when the second ‘a’ goes out of the window.
The time complexity of the above algorithm will be O(N + M) where ‘N’ and ‘M’ are the number of characters in the input string and the pattern respectively.
The space complexity of the algorithm is O(M) since in the worst case, the whole pattern can have distinct characters which will go into the HashMap. In the worst case, we also need O(N) space for the resulting substring, which will happen when the input string is a permutation of the pattern.
Words Concatenation
Given a string and a list of words, find all the starting indices of substrings in the given string that are a concatenation of all the given words exactly once without any overlapping of words. It is given that all words are of the same length.
Example 1
Input: String=”catfoxcat”, Words=[“cat”, “fox”]
Output: [0, 3]
Explanation: The two substring containing both the words are “catfox” & “foxcat”.
Example 2
Input: String=”catcatfoxfox”, Words=[“cat”, “fox”]
Output: [3]
Explanation: The only substring containing both the words is “catfox”.
This problem follows the Sliding Window pattern and has a lot of similarities with Maximum Sum Subarray of Size K. We will keep track of all the words in a HashMap and try to match them in the given string. Here are the set of steps for our algorithm:
- Keep the frequency of every word in a HashMap.
- Starting from every index in the string, try to match all the words.
- In each iteration, keep track of all the words that we have already seen in another HashMap.
- If a word is not found or has a higher frequency than required, we can move on to the next character in the string.
- Store the index if we have found all the words.
The time complexity of the above algorithm will be O(N * M * Len) where ‘N’ is the number of characters in the given string, ‘M’ is the total number of words, and ‘Len’ is the length of a word.
The space complexity of the algorithm is O(M) since at most, we will be storing all the words in the two HashMaps. In the worst case, we also need O(N) space for the resulting list. So, the overall space complexity of the algorithm will be O(M+N).
