Logic

For any sliding window problem, we need to define:

How will our window grow?
At what point will it stop growing and we need to start shrinking or moving the window.

Questions

1. Given an array of positive numbers and a positive number ‘k,’ find the maximum sum of any contiguous subarray of size ‘k’.

Implementation: MaxSumSubArrayOfSizeK

Fix a window of size k with start and end pointers.
Iterate till the window size exceeds k. In the meantime, keep a running sum.
When/If window size is > k, reduce window size by moving start forward and decrementing the running sum.
Update maxSum at the sum time with the max between running sum and current max sum.

2. 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.

Implementation: SmallestSubArrayWithSum

Same logic as #1, just some caveats:

We need to calculate smallestSubArrLen for every iteration till runningSum >= sum because if we wait till the end, the runningSum will actually be lower. The alternative would be wait till runningSum < sum, then add +2 to compensate for the last number that made the runningSum < sum.

Time complexity

O(N+N)

The first N is for the outer loop. In the worst case, it will run through the whole array.
The second N is for the inner loop. In the worst case, after the outer loop has run through the whole array, the inner loop will run through the whole array again.

Space complexity

O(1)

3. Given a string, find the length of the longest substring in it with no more than K distinct characters.

Implementation: LongestSubstring

Same window logic but need to keep track of the chars and their frequency in a map. k = size of the map.

Time complexity

Same logic as #2.

O(N)

Space complexity

O(N) for the map. In the worst case, all chars will be stored in the map.

4. 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.

Implementation: FruitsIntoBaskets

Same logic as #3. Since we can pickup only two types of fruits in a sequence, the k value (from #3) is 2 here.

Time complexity

O(N)

Space complexity

O(1)

5. Given a string, find the length of the longest substring, which has all distinct characters.

Implementation: LongestSubstringWithDistinctChars

Distinct chars would mean that the frequency of each of the chars seen should be 1. If/when we encounter the second occurence of the char, we should start shrinking the window.

The rest is same as #4 and #3.

Time complexity

O(N)

Space complexity

O(N)

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 the longest repeating substring "bbbbb".

Example 2:

Input: String="abbcb", k=1
Output: 4
Explanation: Replace the 'c' with 'b' to have the 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".

Implementation: LongestSubstringAfterReplacement

The window grows till we can replace k chars. But how to know that? For example aabccbb and k=2, if we start from index=0, we can replace 2 chars till index=3 and that will give us the maxLength of 4 chars (all a's).

Once we reach index=3, we can no longer use the window because k=0, aka, we have replaced 2 chars, b and c. At this point, we remove one a and add one c. For this window, we can now replace a and b to get 4 c's. Similarly, if we keep going, we get 4 b's and so on.

So a few observations from here are:

For all the windows we consider, we replace the chars that are left over after we consider the char that repeats the most in that window.
If a char repeats x number of times in a window, say in the first window (aabc), a repeats 2 times. Now when we move the window to abcc, the max repeating char is still 2. If we had got a window like accc, then it would make sense to consider a different max repeating char (c v/s a). Thus, we dont need to track which char is repeating the most per window.

Implementation wise, we take two pointers to track the sliding window and a map to keep count of the chars. We also need a maxLength var to track the output and a maxRepeatingChar var to track the char that's repeating the most.

Time complexity

O(N)

Space complexity

O(N)

Return to Index