For any sliding window problem, we need to define:
Implementation: MaxSumSubArrayOfSizeK
Implementation: SmallestSubArrayWithSum
Same logic as #1, just some caveats:
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.O(N+N)
O(1)
Implementation: LongestSubstring
Same window logic but need to keep track of the chars and their frequency in a map. k = size of the map.
Same logic as #2.
O(N)
O(N)
for the map. In the worst case, all chars will be stored in the map.
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.
O(N)
O(1)
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.
O(N)
O(N)
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:
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.
O(N)
O(N)