Longest Substring Without Repeating Characters - LeetCode(Medium) - Sliding Window Technique!
Hey all! I am solving a LeetCode medium problem today! Let's get right into it.
PermalinkThe Problem
Given a string s, find the length of the longest substring without repeating characters.
Example 1:
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
PermalinkSolutions
PermalinkSolution 1 (not really)
So while solving this first I thought this needed a hash map
to solve it. Because what problem can't be solved with a hash map
! So I was thinking in terms of that. But couldn't figure out a way to cover a lot of edge cases that came with the first algorithm. Long story short, I was looping through the characters tracking the longest substring and when I saw a repeated character I was reinitializing the substring to start from that point itself(which is where I got it wrong).
PermalinkSolution 2
Not long after this, I realized that this was a Sliding Window
problem! So I dropped hash map
and wrote this algorithm instead:
int lengthOfLongestSubstring(string s) {
int i = 0, j = 0;
int maxim = 0;
unordered_set<char> seen;
while (j < s.length()) {
if (seen.find(s[j]) != seen.end()) {
seen.erase(seen.find(s[i]));
i++;
} else {
seen.insert(s[j]);
if (seen.size() > maxim)
maxim = seen.size();
j++;
}
}
return maxim;
}
Let's go through the algorithm line by line. As this is a sliding window
problem, we will define our window between two pointers which are i
and j
. So for example if i = 1
and j = 6
at a certain point in the program, then we have a window consisting of 6 characters
.
So for this, we initialize i
, j
to 0
. We also declare a maxim
variable to store the length of the longest substring which will be our answer.
Then we declare a set
called seen
. This will be used to store the characters in the current window.
And now comes the main section of the algorithm! The while loop. Here's what it does.
We check if j
which is the pointer to the end of the sliding window or the current character is equal to the end of the string, Which means we have checked all substrings. Inside of the loop, We check if the current character(char at j
) is present in the seen
set or not.
If it is present we start removing charters from the window/seen
from its beginning so that the character that's repeating is eventually removed from the seen
set and we keep increasing i
. So the window shrinks.
If the current variable is not in the seen
set, we will insert the character in the seen
set as we have seen it now. And we update maxim
to store the maximum length of the window so far. And we increase j
to the next value. The while loop repeats this until j
is the end of the given string.
That's all for the while loop! At the end of the loop, we return maxim
that will store the maximum length of the substring with non-repeating characters at the end of the loop.
If this didn't make sense on the first read try taking an example string like "pwwkew"
and run it through the algorithm yourself with a pen and paper.
PermalinkSolution 3
Remember on the first try I thought this one can be solved by hash map
? Well, I was right! After solving the problem I checked the solution
tab and I saw the last solution was using a hash map
!
Here's what the solution looks like:
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int i = 0, j = 0;
int m = 0;
int len = s.length();
map<char, int> seen;
while (j < len) {
if (seen.find(s[j]) != seen.end()) {
i = max(seen.find(s[j])->second, i);
}
m = max(m, j - i + 1);
seen[s[j]] = j + 1;
j++;
}
return m;
}
};
The first few lines are the same. i and j
for the window
and m
for the maximum length. len
to store the length of the given string.
This time the seen
variable is actually a map of char
and int
storing the characters we have seen so far and their index + 1
. Inside the while loop, if the current character at j
is in seen
we shift i
to the index
of the repeating character + 1
so index + 1
. And for every iteration, we keep updating m
to store the longest length. and store the current character and its index + 1 in the seen
map and obviously increment j
to keep the loop growing(increasing the length of the window). At the end of the loop, we return m
which at the end of the loop will store the largest substring with non-repeating character's length.
That's it! Told you, hash map
is the way to go!
See you in the next article!