Can you explain the logic mentioned in the approach?

The second step of the problem approach hint suggests, “If we see that the current character being added to the window already exists, shrink the window up till the last index of the character.”. I am unable to understand this from a logical point of view. Can someone explain the logic to solve this with an example string say “pwwkew”?

Hey,

What it means is that if the no of distinct characters in your window is more than K, using the concept of sliding window you need to start shrinking the window from the left so that we can reach a point where the no of distinct characters in the window is <=K.

Suppose the given string is “pwwkew” and K=2 then we start with the left and right pointers initialized with 0. Till the 3rd character of the string, the no of distinct characters were 2 only. At this point left = 0 and right = 2(considering 0th indexing). The longest substring with the given constraints is now 3. When we reach the 4th character, the no of distinct characters is now 3 and thus we need to shrink the window from the left. So, if we shrink the window and make left =1(ie pointing to the 2nd character), the substring again matches the given constraints. We always need to update the length of the longest substring which matches the constraints at every iteration. Now, when we reach the 5th character, the no of distinct character in the current window now reaches 3. So, we again need to shrink the window from the left. Now, we make left = 2(pointing to the 3rd character) but even now the no of distinct characters is 3 in the current window. So, we increase left and make it point to the 4th character(ie left =3) and thus shrink the window. At this point, the no of distinct characters in the given substring is 2. Thus, we get the length of the substring which matches the constraints in the given window to be 2(since left = 3 and right = 4 and the length of the substring is right-left+1 = 2).

This is how the approach is defined.

Thank you.

Closing this topic as your issue has been resolved by the community. If not Kindly un-mark the accepted solution to re-open the topic or feel free to create a new topic and post a link to this topic as a reference.