Can anyone 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” ?

Instead of stepping through with an example, let’s breakdown the answer in smaller parts. The problem is similar to the other longest substring with K distinct characters in that both use sliding windows. The key understanding both problems from two parts: One is using a dictionary to keep track of the index of the character. The second is the actual window itself.

Before we go ahead: If you look at the approach video in the other similar problem (longest K distinct characters) there is a visualization which explains how the window grows and shrinks. Remember we always keep track of the max window size for this problem.

Breakdown:

  • Growing the window is done as long as you keep finding unique characters. This means shrinking the window is only done when a non-unique character is encountered, let’s explore this a bit further. So this statement can be reworded into another way: “Under what conditions do we shrink the size of the window?

  • To understand that, let’s see how the window itself is derived: What is the start and end of the window? And what part does the dictionary play in it? Wait a minute - why do even need the dictionary in the first place? Remember our previous question was around shrinking the window, now we have established that we shrink the window when a non-unique character has been seen. To know whether a character is unique or not, we use a dictionary. So now we are in a position to answer the previous question: “We reduce the size of the window when we encounter non-unique characters. And we maintain if a character is unique or not using a dictionary”.

  • Note that so far, we talked about reducing the size of the window - we did not talk about whether we manipulate the start or end index. So now that we know we are going to reduce the size of the window by manipulating its indices the question now turns into: “Which window index do I manipulate? And how do I use the dictionary to do this?

  • The dictionary usage is this: Use it to keep track of the uniqueness of a character. This means, we can use it to tell if we have already seen a character and but a dictionary has a Key and a Value. If the key is the character itself, what is the value? It is the index of the character in the string. This is important because it brings us to a very important underlying usage of this idea: When we encounter a non-unique character, we can use the dictionary to where we saw that same character previously.

  • So now let us say we finally encounter a character that is already seen. Remember what we have established so far: start index window is at 0, dictionary is keeping track of the index of the characters, all characters are unique except this new one, we have to somehow manipulate window size if we encounter non-unique character, manipulating is done through start or end index of the window. It is very important to keep all of this in mind before looking at the next few steps.

  • So we now know to manipulate start or end window index. Let us consider alternatives: Can we move the start index by 1? No. What if the character repeats in the current window? Can we move the end index back? No, this does not serve any purpose. We also need to keep going forward in the string, and we also don’t know if this is largest window, we also need to keep the characters inside the window unique. So at last we come to the precise nature of the problem you asked: “shrink the window up till the last index of the character”.

  • Given that the window keeps track of unique characters, all we have to do is move the start of the window to index of the character previously seen + 1. This can be done using the dictionary. So the answer we have is: “The second you encounter a non-unique character, you must move the start of the window to a region outside of the index of the same character that was encountered previously”.

  • And finally we have one more question: “Can you find a new window whose size is greater than the window already known?”. This is done simply by running through the rest of the string and repeating the above points.

Hope this helps.

Thank you for such a clear, unambiguous, and detailed explanation!!

Closing this topic as your issue is resolved by the mentor. If it is still not resolved, Kindly un-mark the accepted solution or create a new topic and post this question as a reference link in the description of the new topic.