Crack Leetcode 3: Longest Substring Without Repeating Characters
There is a way to make it easy.
Sometimes they make it look hard, while in fact, there’s always a way you can easily understand. Today, we’ll crack leetcode 3 — Longest Substring Without Repeating Characters— together. Without further ado, let’s get started.
Problem Description:
Ideation:
Step#1: two pointers:
We need to inspect the character in s one by one.
During the process, we use two pointers: start, and end, to indicate the current range we are inspecting.
Note that the end pointer also acts as our index pointer.
Then, we check if the character s[end] has repeats in our range [start, end) already. If NO, then for now our longestSubstring =(end - start)+1 .
If YES, then we need to narrow our range by moving start forward, until this character is outside of our range, and then we inspect the next character.
Step#2: dictionary:
For above idea, how do we check if a character has repeats in our range? The fastest way is to use a dictionary:
There is only one problem: what if the char is in dictionary, but not in our range?
There are two ways to solve it:
Solution #1:
All the time, we make sure that our dictionary only contains chars within our range [start, end).
That means, upon seeing a character with duplicates in our range, we need to do one more thing: update our dictionary by deleting data outside of our new range, so that the dictionary only contains characters within range [start, end).
— Python Code:
`
— Complexity Analysis:
#Time Complexity:
- Best-Case:
Best case is when there’s no repeats in s. Then we only need to go over s once, and we do constant number of operations for each character. Therefore Best Case time complexity is O(N).
- Worst-Case:
Worst case is when every character is a repeat in s. We still need to go over s once, and we do 2 more operations (delete in dict, move start) for each character, but that’s still a constant number of operations. Therefore Worst Case time complexity is O(N).
- Average-Case:
sum up the expectations for all the possible cases, and when N->+oo, the sum can be described with O(N). Therefore the average time complexity is O(N).
#Space Complexity:
The auxiliary space is taken mainly by the dictionary. The maximum space it needs is number of distinct chars in s. Therefore space complexity = O(N).
`
Solution #2:
The dictionary still contains everything up to now, no deletion.
Instead, we check the index of this replica. If the index of this replica is not within range [start, end), then we consider it’s not in the dictionary, thus we can achieve the same result with solution #1.
For the example below:
a has a replica in dict. However, since dict[a]=0 < start_index which is 3, we say no replica exists in range [start, end), thus we just update its value, and update the current longestSubstring.
— Python Code:
`
— Complexity Analysis:
- Time Complexity:
Same as above, O(N). Note that even though time complexity is the same with solution #1, the practical runtime is faster this way.
- Space Complexity: same as above, O(N).
Solution #3:
This is a variation of solution#2. It has a different definition in the meaning of key-value pair.
Instead of storing the current index as value, we now save (current index+1), which means suppose this char found a replica in the future, then this is the position start pointer should go.
— Python Code:
And if we use a large array instead of dictionary for the same function, then we get this:
For the code above, the array called index, replaced the role of dictionary. For each char, the ascii code of this char acts as the key, and (current index +1) acts as value.
Since an array has no key-value pair, we just used the index in the array as key.
For example: a in string “abc”. if in dictionary, we add dict[a]=0, however with array, we say array[ascii code of a] = 0+1.
`
— Complexity Analysis:
- Time Complexity: Same with above, O(N).
- Space Complexity:
if we use dictionary, it’s same as above, O(N).
if we use a large array, then it’s constant space consumption, thus Space complexity is O(1).
The End:
Thanks for reading! Please check our articles more often, if you’d like to support our work — and we’ll see you in the next one!
