LeetCode longest substring without repeating characters : explanations and solutions with Cpp/Java/Python
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 sub-string 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
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:
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 is same with C++ version:
Preparing for an interview? Checkout this!