Sliding Window¶
The Sliding Window technique is used to efficiently process subarrays or substrings of a fixed or variable size.
Instead of recomputing results for every window, the window slides across the array/string, updating results incrementally.
This technique is widely used in string processing, subarray problems, and optimization tasks.
1. Medium Problems¶
/*
Question:
Given a string s, find the length of the longest substring without repeating characters.
Approach:
- We can use a sliding window approach to solve this problem.
- We maintain a window that contains only unique characters.
- We use a hash map to store the frequency of characters in the current window.
- We iterate through the string and expand the window by adding one character at a time.
- If we encounter a repeating character, we shrink the window from the left until the character is no longer in the window.
- We keep track of the maximum window size encountered so far and return it as the result.
Example:
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
CODE:-
*/
int lengthOfLongestSubstring(const string& s) {
int ans = 0;
unordered_map<char, int> mp;
int start = 0;
for (int i = 0; i < s.size(); i++) {
mp[s[i]]++;
while (mp.size() < i - start + 1) {
mp[s[start]]--;
if (mp[s[start]] == 0)
mp.erase(s[start]);
start++;
}
if (mp.size() == i - start + 1)
ans = max(ans, i - start + 1);
}
return ans;
}
// Complexity Analysis:
// - The time complexity of this algorithm is O(N), where N is the length of the input string `s`. We iterate through each character of the string once.
// - The space complexity is O(M), where M is the number of unique characters in the string `s`. The unordered map `mp` can store up to M key-value pairs.
/*QUESTION:
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.
Example 1:
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]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.
APPROACH:
1. Initialize variables zeroCnt, start, and ans.
2. Iterate through the array nums:
- If the current element is 0, increment zeroCnt.
- Enter a while loop to adjust the start index until zeroCnt becomes less than or equal to k.
- During the adjustment, decrement zeroCnt if the element at the start index is 0.
- Update ans by taking the maximum of the current ans and the length of the current subarray if zeroCnt is less than or equal to k.
3. Return the maximum length of consecutive 1's (ans).
CODE:*/
int longestOnes(vector<int>& nums, int k) {
int zeroCnt = 0, start = 0, ans = 0;
for(int i = 0; i < nums.size(); i++) {
if(nums[i] == 0)
zeroCnt++;
while(zeroCnt > k) {
if(nums[start] == 0)
zeroCnt--;
start++;
}
if(zeroCnt <= k)
ans = max(ans, i - start + 1);
}
return ans;
}
/*
COMPLEXITY ANALYSIS:
- Time complexity: O(N), where N is the length of the input array nums. We iterate through the array once.
- Space complexity: O(1), as we are using a constant amount of additional space to store variables.
*/
/*QUESTION:
You are visiting a farm that has a single row of fruit trees arranged from left to right. The trees are represented by an integer array fruits of size N, where fruits[i] is the type of fruit the ith tree produces.
You want to collect as much fruit as possible. However, the owner has some strict rules that you must follow:
1. You only have two baskets, and each basket can only hold a single type of fruit. There is no limit on the amount of fruit each basket can hold.
2. Starting from any tree of your choice, you must pick exactly one fruit from every tree (including the start tree) while moving to the right. The picked fruits must fit in one of the baskets.
3. Once you reach a tree with fruit that cannot fit in your baskets, you must stop.
Given the integer array fruits, return the maximum number of fruits you can pick.
Example 1:
Input: N = 3, fruits[] = {2, 1, 2}
Output: 3
Explanation: We can pick fruits from all three trees.
APPROACH:
1. Initialize an unordered_map mp to track the frequency of fruit types.
2. Initialize variables ans and start to keep track of the maximum number of fruits and the start index of the subarray.
3. Iterate through the fruit trees using a sliding window approach:
- Increment the frequency of the current fruit type in the map.
- Enter a while loop to adjust the start index until the number of fruit types in the map becomes more than 2.
- During the adjustment, decrement the frequency of the fruit type at the start index and remove it from the map if the frequency becomes 0.
- Update the ans by taking the maximum of the current ans and the length of the current subarray if the number of fruit types in the map is at most 2.
4. Return the maximum number of fruits (ans).
CODE:*/
int totalFruits(int N, vector<int>& fruits) {
unordered_map<int, int> mp;
int ans = 0, start = 0;
for(int i = 0; i < fruits.size(); i++) {
mp[fruits[i]]++;
while(mp.size() > 2) {
mp[fruits[start]]--;
if(mp[fruits[start]] == 0)
mp.erase(fruits[start]);
start++;
}
if(mp.size() <= 2)
ans = max(ans, i - start + 1);
}
return ans;
}
/*
COMPLEXITY ANALYSIS:
- Time complexity: O(N), where N is the number of fruit trees. We iterate through the fruit trees once using the sliding window approach.
- Space complexity: O(1) or O(2), as the size of the map can be at most 2 since we only have two baskets.
*/
/*QUESTION:
You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.
Return the length of the longest substring containing the same letter you can get after performing the above operations.
Example 1:
Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.
APPROACH:
1. Create an unordered_set ltrs to store all unique letters in the given string s.
2. Initialize a variable ans to keep track of the maximum length of the substring.
3. Iterate through each letter ltr in the set ltrs:
- Initialize variables start and ltrCnt to track the starting index of the current substring and the count of ltr in the substring.
- Iterate through each character in the string s:
- If the character is equal to ltr, increment ltrCnt.
- Enter a while loop to adjust the start index until the number of characters in the substring that are different from ltr is more than k.
- During the adjustment, if the character at the start index is equal to ltr, decrement ltrCnt.
- Increment the start index.
- If the length of the current substring minus ltrCnt is at most k, update ans by taking the maximum of ans and the length of the current substring.
4. Return the maximum length of the substring (ans).
CODE:*/
int characterReplacement(string s, int k) {
unordered_set<char> ltrs;
for(auto it : s)
ltrs.insert(it);
int ans = 0;
for(auto ltr : ltrs) {
int start = 0, ltrCnt = 0;
for(int i = 0; i < s.size(); i++) {
if(s[i] == ltr)
ltrCnt++;
while((i - start + 1) - ltrCnt > k) {
if(s[start] == ltr)
ltrCnt--;
start++;
}
if((i - start + 1) - ltrCnt <= k)
ans = max(ans, i - start + 1);
}
}
return ans;
}
/*
COMPLEXITY ANALYSIS:
- Time complexity: O(N * L), where N is the length of the string s and L is the number of unique letters in the string. We iterate through the string and perform the sliding window operation for each unique letter.
- L can have the max value of 26, so we can say the complexity would be O(N * 26) i.e O(N).
- Space complexity: O(L), as we store the unique letters in the set ltrs.
*/
/*QUESTION:
Given a binary array nums and an integer goal, return the number of non-empty subarrays with a sum equal to the goal.
Example 1:
Input: nums = [1,0,1,0,1], goal = 2
Output: 4
Explanation: The 4 subarrays are bolded and underlined below:
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]
APPROACH:
1. Create an unordered_map mp to store the prefix sum and its frequency.
2. Initialize a variable prefSum to keep track of the prefix sum.
3. Initialize a variable cnt to keep track of the count of subarrays with a sum equal to the goal.
4. Iterate through each element nums[i] in the array:
- Update prefSum by adding nums[i].
- Check if prefSum is equal to the goal, if so, increment cnt.
- Check if the difference between prefSum and goal (prefSum - goal) exists in the map.
- If it exists, increment cnt by the frequency of (prefSum - goal) in the map, as this would mean we have found subarrays with a sum equal to the goal.
- Increment the frequency of prefSum in the map.
5. Return cnt, which represents the number of non-empty subarrays with a sum equal to the goal.
CODE:*/
int numSubarraysWithSum(vector<int>& nums, int goal) {
unordered_map<int, int> mp;
int prefSum = 0, cnt = 0;
for(int i = 0; i < nums.size(); i++) {
prefSum += nums[i];
if(prefSum == goal)
cnt++;
if(mp.find(prefSum - goal) != mp.end())
cnt += mp[prefSum - goal];
mp[prefSum]++;
}
return cnt;
}
/*
COMPLEXITY ANALYSIS:
- Time complexity: O(N), where N is the size of the input array nums. We traverse the array once and perform constant time operations in the loop.
- Space complexity: O(N), as the worst-case scenario would be that all prefix sums are distinct, so the map mp would store N prefix sums.
- we can reduce the space complexity to O(1) if we use this countOfSubarrays with atmost sum = k - atmost sum = k-1
- which will return in countofSubarrays with sum exactly K, but this won't work if array has -ve elements
*/
QUESTION:
/*Given an array of integers nums and an integer k, a continuous subarray is called nice if there are k odd numbers in it. Return the number of nice subarrays.
Example 1:
Input: nums = [1,1,2,1,1], k = 3
Output: 2
Explanation: The only subarrays with 3 odd numbers are [1,1,2,1] and [1,2,1,1].
APPROACH:
1. Define a helper function called atMostK, which calculates the number of subarrays with at most k odd numbers.
2. Initialize variables start to 0, oddCnt to 0, and ans to 0.
3. Iterate through each element nums[i] in the array:
- If nums[i] is odd, increment oddCnt by 1.
- While oddCnt is greater than k, move the start pointer and decrement oddCnt if the element at nums[start] is odd. This ensures that we maintain at most k odd numbers in the subarray.
- Add the count of subarrays from start to i (i - start + 1) to ans.
4. Return ans, which represents the number of subarrays with at most k odd numbers.
5. In the numberOfSubarrays function, return the difference between atMostK(nums, k) and atMostK(nums, k - 1) to get the number of nice subarrays.
CODE:*/
int atMostK(vector<int>& nums, int k) {
int start = 0, oddCnt = 0, ans = 0;
for(int i = 0; i < nums.size(); i++) {
if(nums[i] % 2 != 0)
oddCnt++;
while(oddCnt > k) {
if(nums[start] % 2 != 0)
oddCnt--;
start++;
}
ans += i - start + 1;
}
return ans;
}
int numberOfSubarrays(vector<int>& nums, int k) {
return atMostK(nums, k) - atMostK(nums, k - 1);
}
/*
COMPLEXITY ANALYSIS:
- Time complexity: O(N), where N is the size of the input array nums. We traverse the array once in both the atMostK function and the numberOfSubarrays function.
- Space complexity: O(1), as we use constant extra space throughout the algorithm.
*/
/*
QUESTION:
Given a string s consisting only of characters 'a', 'b', and 'c', you need to count the number of substrings that contain at least one occurrence of all these characters.
APPROACH:
To count the number of substrings with at least one occurrence of 'a', 'b', and 'c', we can use a sliding window approach.
1. Create a helper function, countOfUnvalidSubstrings, which counts the number of substrings that do not contain all three characters.
- Initialize an unordered_map, mp, to keep track of the counts of characters in the current window.
- Initialize start to 0 and ans to 0.
- Iterate over the string from left to right:
- Increment the count of the current character in mp.
- If the number of unique characters in mp exceeds 2, it means we have found an invalid substring.
- Decrement the count of the character at the start of the window in mp.
- If the count becomes zero, remove the character from mp.
- Move the start of the window to the next position.
- Add the length of the current window to ans.
- Return ans.
2. In the main function, numberOfSubstrings:
- Calculate the total number of substrings, cntOfTotalSubstrings, using the formula (n * (n + 1)) / 2, where n is the length of the string.
- Subtract the count of invalid substrings obtained from countOfUnvalidSubstrings from cntOfTotalSubstrings.
- Return the resulting count.
*/
int countOfUnvalidSubstrings(string& s) {
unordered_map<char, int> mp;
int start = 0, ans = 0;
for (int i = 0; i < s.size(); i++) {
mp[s[i]]++;
while (mp.size() > 2) {
mp[s[start]]--;
if (mp[s[start]] == 0)
mp.erase(s[start]);
start++;
}
ans += i - start + 1;
}
return ans;
}
int numberOfSubstrings(string s) {
long long n = s.size();
int cntOfTotalSubstrings = (n * (n + 1)) / 2;
return cntOfTotalSubstrings - countOfUnvalidSubstrings(s);
}
/*
COMPLEXITY ANALYSIS:
- Time complexity: O(n), where n is the length of the string s. We iterate over the string once.
- Space complexity: O(1), as the extra space used is constant throughout the algorithm.
*/
/*
QUESTION:
You are given an array of cards, each with an associated number of points. You can take exactly k cards, either from the beginning or from the end of the row. Your goal is to maximize the sum of the points of the cards you have taken. Return the maximum score you can obtain.
APPROACH:
To maximize the score, we need to minimize the sum of the discarded cards. We can find the minimum sum of a subarray of size (n - k) using a sliding window approach.
1. Create a helper function, minimumSumOfSizeK, which finds the minimum sum of a subarray of size k.
- Initialize ans to INT_MAX, currsum to 0, and start to 0.
- Iterate over the array from left to right:
- Add the current element to currsum.
- If the size of the current window (i - start + 1) exceeds k, remove the element at the start of the window from currsum and move the start to the next position.
- If the size of the current window is k, update ans with the minimum of ans and currsum.
- Return ans.
2. In the main function, maxScore:
- Calculate the total sum of all the cards, totalSum.
- Calculate the size of the discarded cards, windowSize, which is (n - k).
- Find the minimum sum of a subarray of size windowSize using the minimumSumOfSizeK function and store it in discardedSum.
- Return the maximum score, which is (totalSum - discardedSum).
COMPLEXITY ANALYSIS:
- Time complexity: O(n), where n is the size of the cardPoints array. We iterate over the array once to calculate the total sum and find the minimum sum of a subarray.
- Space complexity: O(1), as the extra space used is constant throughout the algorithm.
*/
int minimumSumOfSizeK(vector<int>& arr, int k) {
int ans = INT_MAX, currsum = 0, start = 0;
for (int i = 0; i < arr.size(); i++) {
currsum += arr[i];
while ((i - start + 1) > k) {
currsum -= arr[start];
start++;
}
if ((i - start + 1) == k)
ans = min(ans, currsum);
}
return ans;
}
int maxScore(vector<int>& cardPoints, int k) {
int totalSum = 0;
for (auto it : cardPoints) {
totalSum += it;
}
int windowSize = cardPoints.size() - k;
int discardedSum = minimumSumOfSizeK(cardPoints, windowSize);
return totalSum - discardedSum;
}
2. Hard Problems¶
/*
QUESTION:
Given a string 'str' and an integer 'K', find the length of the largest substring with at most 'K' distinct characters.
EXAMPLE:
For example, if we are given 'str' = "abbbbbbc" and 'K' = 2, the substrings that can be formed are ["abbbbbb", "bbbbbbc"]. Hence, the answer is 7.
APPROACH:
We can use a sliding window approach to solve this problem.
1. Create a function, kDistinctChars, that takes 'k' and the input string 's' as parameters.
- Initialize an unordered_map, mp, to store the frequency of characters.
- Initialize 'start' to 0 and 'ans' to 0.
- Iterate over the string from left to right:
- Increment the frequency of the current character in the map.
- If the number of distinct characters in the map exceeds 'k', move the 'start' pointer to the right and remove characters from the map until the number of distinct characters becomes equal to 'k'.
- Update 'ans' with the maximum length of the substring (i - start + 1).
- Return 'ans', which represents the length of the largest substring with at most 'k' distinct characters.
COMPLEXITY ANALYSIS:
- Time complexity: O(n), where n is the length of the string 's'. We iterate over the string once using the sliding window approach.
- Space complexity: O(k), as the space used by the unordered_map is proportional to the number of distinct characters, which can be at most 'k'.
*/
int kDistinctChars(int k, string &s) {
unordered_map<char, int> mp;
int start = 0, ans = 0;
for (int i = 0; i < s.size(); i++) {
mp[s[i]]++;
while (mp.size() > k) {
mp[s[start]]--;
if (mp[s[start]] == 0)
mp.erase(s[start]);
start++;
}
ans = max(ans, i - start + 1);
}
return ans;
}
/*
QUESTION:
Given an integer array 'nums' and an integer 'k', find the number of good subarrays of 'nums'.
A good array is an array where the number of different integers in that array is exactly 'k'.
For example, [1,2,3,1,2] has 3 different integers: 1, 2, and 3.
A subarray is a contiguous part of an array.
EXAMPLE:
Input: nums = [1,2,1,2,3], k = 2
Output: 7
Explanation: Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2]
APPROACH:
We can solve this problem using a sliding window approach.
1. Create a function, kDistinctIntegers, that takes 'k' and the input vector 's' as parameters.
- Initialize an unordered_map, mp, to store the frequency of elements.
- Initialize 'start' to 0 and 'ans' to 0.
- Iterate over the vector from left to right:
- Increment the frequency of the current element in the map.
- If the number of distinct elements in the map exceeds 'k', move the 'start' pointer to the right and remove elements from the map until the number of distinct elements becomes equal to 'k'.
- Update 'ans' by adding the number of subarrays that can be formed with exactly 'k' distinct integers, which is equal to (i - start + 1).
- Return 'ans', which represents the total number of good subarrays.
2. Create a function, subarraysWithKDistinct, that takes 'nums' and 'k' as parameters.
- Return the difference between the number of good subarrays with 'k' distinct integers and the number of good subarrays with 'k-1' distinct integers, which can be calculated using the kDistinctIntegers function.
COMPLEXITY ANALYSIS:
- Time complexity: O(n), where n is the length of the input vector 'nums'. We iterate over the vector once using the sliding window approach.
- Space complexity: O(k), as the space used by the unordered_map is proportional to the number of distinct elements, which can be at most 'k'.
*/
int kDistinctIntegers(int k, vector<int> &s) {
unordered_map<int, int> mp;
int start = 0, ans = 0;
for (int i = 0; i < s.size(); i++) {
mp[s[i]]++;
while (mp.size() > k) {
mp[s[start]]--;
if (mp[s[start]] == 0)
mp.erase(s[start]);
start++;
}
ans += i - start + 1;
}
return ans;
}
int subarraysWithKDistinct(vector<int>& nums, int k) {
return kDistinctIntegers(k, nums) - kDistinctIntegers(k - 1, nums);
}
/*
QUESTION:
Given two strings 's' and 't' of lengths 'm' and 'n' respectively, find the minimum window substring of 's' that contains all the characters of 't' (including duplicates). If there is no such substring, return an empty string.
EXAMPLE:
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string 't'.
APPROACH:
We can solve this problem using a sliding window approach.
1. Create a function, minWindow, that takes 's' and 't' as parameters.
- Initialize an unordered_map, mp, to store the frequency of characters in 't'.
- Iterate over 't' and update the frequencies in the map.
- Initialize 'count' to the number of unique characters in 't'.
- Initialize 'start' to 0 and 'minlen' to INT_MAX.
- Initialize 'substrBegin' to 0, which represents the starting index of the minimum window substring.
- Iterate over 's' from left to right:
- Decrement the frequency of the current character in the map.
- If the frequency becomes 0, decrement 'count'.
- Check if 'count' becomes 0, indicating that we have found a window containing all characters of 't'.
- If the current window length is smaller than 'minlen', update 'minlen' and 'substrBegin' to the current window length and starting index respectively.
- Move the 'start' pointer to the right, increment the frequency of the character at 'start' in the map, and increment 'count' if the frequency becomes greater than 0.
- Return the minimum window substring by using the substr function on 's' with 'substrBegin' and 'minlen' as parameters.
- If 'minlen' is still INT_MAX, return an empty string.
COMPLEXITY ANALYSIS:
- Time complexity: O(m + n), where m is the length of 's' and n is the length of 't'. We iterate over both strings once using the sliding window approach.
- Space complexity: O(n), as the space used by the unordered_map is proportional to the number of unique characters in 't', which can be at most 'n'.
*/
string minWindow(string s, string t) {
unordered_map<char, int> mp;
for (auto it : t) {
mp[it]++;
}
int count = mp.size();
int start = 0, minlen = INT_MAX;
int substrBegin = 0;
for (int i = 0; i < s.size(); i++) {
mp[s[i]]--;
if (mp[s[i]] == 0)
count--;
while (count == 0) {
if (i - start + 1 < minlen) {
substrBegin = start;
minlen = i - start + 1;
}
mp[s[start]]++;
if (mp[s[start]] > 0) {
count++;
}
start++;
}
}
return (minlen == INT_MAX) ? "" : s.substr(substrBegin, minlen);
}