educative.io

Educative

Can't understand why we don't calculate the maxRepeating for each window


This is what I came up with.

@Design_Gurus
I fail to understand why wouldn’t we need to reevaluate the maxChar in each window.
Instead, the solution given seems to be just keeping track of the maxRepeating char across all windows. Even if we end up deleting this character from the current window, it doesn’t account for it. Please help me bridge the disconnect.

3 Likes

Here is my explanation.
maxLength can be redefined as maxChar + k. Now there are two possible scenarios as we move the sliding window along the string:

  1. maxChar in the new window is greater than the previous maxCahr. In this case the maxChar is replaced with the new value
  2. maxChar is less. In this case we don’t care because the resulting maxLength will be smaller Aaccording to the definition above maxLength = maxChar + k. Since k is constant and maxChar is smaller, maxLength will be smaller as well. So we ignore this case.
1 Like

If we had to also return the string which contained maxChar + k - we had to track maxLength inside the window.
@Konstantin_Shilovski Thx for the explanation :pray:

Take a look @ Longest Substring with Same Letters after Replacement (hard)