If the both the questions Longest substring with same characters after replacement and longest subarray with ones after replacement, then why does maxOnesCount gets decremented when maxRepeatLetterCount of Longest substring with same characters after replacement is not?
1 Like
Hello @banu_kiran
When we shrink the window that is k, we can only replace the k number of 0’s with 1’s. Suppose if we can replace only one 0 with 1, it is likely that our maxOnesCount will be lesser.
I hope this will help.
Happy Learning
@Muhammad_Ali_Shahid can you clarify it further please?
The confusion is because it looks like the algorithm should essentially be the same, but for 0s and 1s, maxRepeatLetterCount is not decremented.
In the other problem it required quite some mental gymnastic to understand why this counter is not decremented, and here if we do not do it, solution is wrong.
Thanks.
I think I got it.
The difference compared to the solution in Longest Substring with Same Letters after Replacement is that there we had a frequency map, and maxRepeatLetterCount is not constantly increasing whenever most frequent character appears on the right. It is because maybe it has been dropped in the previous iteration where we had
letterFrequencyMap.put(leftChar, letterFrequencyMap.get(leftChar) - 1);
Because of that counter will not be increased, but historical maximum will be kept
letterFrequencyMap.put(rightChar, letterFrequencyMap.getOrDefault(rightChar, 0) + 1);
maxRepeatLetterCount = Math.max(maxRepeatLetterCount, letterFrequencyMap.get(rightChar));
For this problem (0s and 1s) we need to decrement because the counter will continuously grow with every new 1.