Longest Substring Without Repeating Characters
- 2 min read
- String
- Blind75
- LC-Medium
- Hash Table
- Sliding Window
3 years ago
Approach 1: Sliding Window
Use a sliding window to iterate through substrings and use a set to keep track of whether or not a character was already seen before. If character in a substring was already seen, increment left pointer until the substring doesn't contain the new character anymore.
Approach 2: Sliding Window Optimized
-
Similar to Approach 1, but instead of using a set to keep track of whether or not a character was already seen, use a dictionary to keep track of the index of each character. If the character is already seen, set the left pointer to the index of the character + 1. This way, we don't have to iterate through the set to remove the character.
-
Extra condition: if the character is already seen and the index of the character is less than the left pointer, then we don't need to update the left pointer.
Basically l can't move left. It can only move right. So either move it right or leave it unchanged. You only move it right when l is less than the current repetition. If l has somehow moved ahead then there's no need to move it left. For example in abba. When the second a is encountered, l has moved ahead from first a. But the map still remembers that as the last seen a. Now just to eliminate the left a if we move l by just 1 then it will land on first b. l moved backwards. Before it was on second b and now it is on first b. Just don't update it in this case. Just update the repeated character position in the map and now back to normal, l has become less than the next repeating a, so now l can move, if it sees another a.