For any sliding window problem, we need to define:
Same logic as #1, just some caveats:
smallestSubArrLenfor 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.
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) for the map. In the worst case, all chars will be stored in the map.
Same logic as #3. Since we can pickup only two types of fruits in a sequence, the k value (from #3) is 2 here.
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.
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".
The window grows till we can replace k chars. But how to know that? For example
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.
Return to Index