LeetCode longest substring without repeating characters : explanations and solutions with Cpp/Java/Python
Challenge Description

Explanation
Naive solutions
According to problem description, the first solution should be enumerating all the ranges of the string, check whether characters in range[i, j] are unique, if it’s true, we compute the distance and compare it with the current distance, choose the max one as answer.
But how to check whether a substring is constructed with all unique characters? HashSet
is need here, so the pseudo code is:

It’s easy to figure out, there are three loop range in pseudo code.
Time complexity: $O(N^3)$ Space complexity: We most need $O(K)$ space, where K is the number of different characters, 26 is enough for letters.
Optimization: reduce the double check with hashmap
Notice in the naive solution, we have a gap double checked in range. For example, we checked range[1, 4) in first loop, we also checked range [2, 4) in later loop, that’s what we can optimize on time complexity.
Actually we can maintain a window slice, tracking all unique characters in the windows, if next character can be found in the previous window, which means we need to update the window to current position. How can we quickly found out whether a character occurs in window? A hashset
or hashmap
can be used here.
Here we come out the C++ version:

Take a example input ‘abccde’, it’s output should be:

The time complexity is: $O(N)$, and space complexity is same as naive solution.
An alternative implementation is use hashmap
to store the index of characters, which can be fetched to check the distance of range:

Other optimization
If characters have fixed range, we just use a table replace the hashmap, using table will also perform better, and more suitable for C programming languages which don’t have hashmap in standard library.
Java
Java is same with C++ version:

Python

Join my Email List for more insights, It's Free!😋