Difficulty: Hard
Category: Strings
Step 1: Grasping the Problem
We need to get the length of the maximum substring from a given string where the substring must not have any duplicate characters. We do not need to return the substring. So we do not need to care about the order of the substrings.
As we do not need the string, we just need to take care of the frequencies of the largest string. In a more “targeting towards the solution” way, we need to keep the characters of largest string so far stored so that when we try to make the string larger by concatenating more characters, we can make sure that it is not already in the stored characters. Hashset is a perfect datastructure for the following use. Python has built in set
for this.
Also, a substring is a sequential subset of the given string string
. And we need to expand this sequential subset as large as possible. This tells us that a sliding window maximization approach is best to solve this problem.
In a sliding window maximization problem, we start from the first element with window size one. Then we try to expand the window by onebyone element until we can’t. Then we shrink the window until again we become able to increase it. Everytime we increase, we could track both the largest substring and it’s length. Below is a small demonstration of what a sliding window approach would look like.
Step 2: Sliding Window Initialization
A sliding window needs four things to operate.
 The left boundary of the window (
left
for this solution).  The right boundary of the window (
right
for this solution).  The target variable (
longest
for this solution). This variable stores the target we want to get from the window. It can be many variables or states like the starting and ending of the substring. But in this solution, we only need the length of the largest substring.  Any intermediate variables to assert the conditions of window expanding/shrinking ability. In this problem, it is
current_chars
which stores the characters of the largest string.
So the initialization will look something like this:


Step 3: Loop for the window
The sliding window will run until we have reached the end of the string. But do we need the left
variable to reach the end too? No, because we need only the largest value. Moving left
towards end will only shrink the window making longest
smaller that it is now.
So looping until right
has reached end will suffice.


Step 4: Expand the window
We can only expand the window when the new character is not in current_chars
list. After checking if we can add the character, we need to add that character to current_chars
to check for new characters in the future.
We also need to increase longest
if it becomes larger than the previous one. And finally we need to expand the window boundary to one character right.


Step 5: Shrink the window
If we cannot expand the window, we will need to shrink it. We will shrink it until the new character is removed from current_chars
. This can be taken care by the while loop we created earlier. And after removing the leftmost character of the window, we will move the left boundary of the window one character right.


Step 6: Return longest
After the while loop ends, we will surely get the longest substrings length. We will return it after the while loop.


Every sliding window problem takes O(n)
time itself, where n
is the length of the string. Inside the loop, we are making a lookup in a hashset and incrementing and decrementing variable. All these take O(1)
time. So the time complexity of the algorithm is O(n)
and space complexity is also O(n)
in the worst case. The program is given below.





