3. Longest Substring Without Repeating Character
Introduction
Leetcode problems can feel pretty tricky at times. Almost as if the Lord of Chaos conjured up this unsolvable riddle himself. Solutions sometimes don’t really help either. They don’t always explain the solution in a step-by-step format. No worries, friends will get through this sandstorm of a problem like the determined camels of North Africa.
The Prompt
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.-------------------------------------------Example 2:Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.--------------------------------------------Example 3:Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.-----------------------------------------------Example 4:Input: s = ""
Output: 0
My Thoughts
Like I always, we should read the prompt and examples to each problem. Spend time understanding what the author is asking. Patterns will begin to emerge, which you can pair with what you know about algorithms and data structures.
Given a string s, find the length of the longest substring without repeating characters.The prompt is simple and straightforward. The longest substring without repeats got it. But things are always so simple. I immediately would like to see some examples to help illustrate the hidden complexity here.
Example 1:Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
The First example syncs up nicely with the prompt. We see the input, output, and why we get the return value.
Example 2:Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
The Second example gives us an edge case, so we want to be mindful of this. “Spamming” a single letter should return a count of 1.
Example 3:Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
Hmm… now it gets interesting. The subsequence vs. substring makes sense; we need consecutive values. So positioning in the string matters. I personally had to look at this a few times.
Why was ‘wke’ the longest substring? What does that say about how we move through this string? More importantly, where do we restart the count once we find a duplicate character? The answer here states we start at the 2nd W. That’s important to note.
Example 4:Input: s = ""
Output: 0
This example makes sense and is an edge case. Let’s keep that in mind.
Reviewing what I’ve broken down:
- we need the longest substring without repeats
- Input: a string
- Output: a count should be an integer/number
- The count should be based on a substring, NOT a subsequence.
- Consecutive values matter.
- If we find a duplicate character, we reset and re-start counting on the duplicate character.
- If the Input: empty string, then Output: zero.
Breakdown
Let’s get through this sandstorm of confusion. Let’s take a moment to take a breath, clear our minds of all bad thoughts or distractions, and calmly walk into this level-headed.
First off, I realized simple iteration wouldn’t cut it. We need to reference all the string characters we’ve visited as we visit each new character. So nested loops could work, but they aren’t really efficient. Perhaps if we used a single loop …
We should also create 2 pointers. The first for checking the current character. It’s on with what we already iterated through. The Second should move if we found a match. The start of the substring should move by 1 for each character that’s a match.
Maps, Objects, and Sets are great for this kind of thing. We can store values and quickly look up what’s inside. Javascript some already “baked-in” to the language for us. So we won’t need to build a custom data structure, NICE!
Since we care about unique characters, we will use Sets because that just so happens to be what they are really good at. We will also need to return when the function is done running.
- Iteration with a loop is needed.
- Using some data structure like a hash
- mapping would be nice, great run-time for searching
- duplicates are a problem; let’s use a Set!
- pointer for looking at each letter
- pointer for tracking when the substring starts
- return a counter with the longest substring value
const lengthOfLongestSubstring = function(s) {
let start = 0;
let seeker = 0;
let set = new Set();
let counter = 0;
...Let’s start with setting up our pointers, Set, and counter with let variables. Notice that we set both pointers to zero, which will double as indices will use later. The seeker will compare characters; the start will show us where the substring starts.
const lengthOfLongestSubstring = function(s) {
let start = 0;
let seeker = 0;
let set = new Set();
let counter = 0;
while (seeker < s.length ) {
}
return counter
};Let’s set up our loop. I think a while loop should do just fine; we want this loop's condition to be based on the length of the Input(the string we start with). One pass should be all we need.
const lengthOfLongestSubstring = function(s) {
let start = 0;
let seeker = 0;
let set = new Set();
let counter = 0;
while (seeker < s.length ) {
if() {
} else {
}
}
return counter
};Next will set up an if/else statement. The idea is we want to divide logic based on whether we found a match with our “seeker” pointer or not.
... while (seeker < s.length ) {
if(!set.has(s.charAt(seeker))) {
...Let’s deal with not finding any matches first. We want to check our set with the .has()method. This comes baked into Set(). Next we use the s(Input string) + .charAt() method. This will combination will grab a character of our input string with a given index.
See how we can use our seeker(which is an index value) to grab the current character? This cuts down writing code. Pretty cool, huh?
In the if statement will use the bang or ! operator to verse the logic. It’s subtle to write, but what we are saying here is …
... while (seeker < s.length ) {
if(!set.has(s.charAt(seeker))) {
set.add(s.charAt(seeker)); ...If we don’t find any characters in our set, let’s add this character.
See how we are using the .add() method + s(Input string) + .charAt() method. Same idea, but with an addition of the .add() which comes built into Set(), as well.
... if(!set.has(s.charAt(seeker))) {
set.add(s.charAt(seeker));
counter = Math.max(counter, set.size);
seeker++; ...Now we need to count each addition to our Set. It’s important to note that
there may be certain instances where our counter or our set size will be different numbers. We would need to return the higher value, in this case, with this problem. Let’s use Math.max(). This returns the highest value of the two.
We will also move our Seeker pointer along by 1. Pretty easy to do with an increment operator or ++.
... if(!set.has(s.charAt(seeker))) {
set.add(s.charAt(seeker));
counter = Math.max(counter, set.size);
seeker++;
} else {
set.delete(s.charAt(start));
start++;
}...So what happens when we find a match? If you remember, we said we would have to move our start pointer by one. Our set would also need to reflect this. This means we need to delete the character inside our Set as well!
Same idea with this implementation:
.delete() method + s(Input string) + .charAt() method + start. Delete is a baked-in method just like Add or Has. It will remove the target character from the set. We use an index provided by our start pointer. Let’s also increment our start pointer with our increment operator or ++.
while (seeker < s.length ) {
if(!set.has(s.charAt(seeker))) {
set.add(s.charAt(seeker));
counter = Math.max(counter, set.size);
seeker++;
} else {
set.delete(s.charAt(start));
start++;
}
}
};That’s it! We did it. Not so bad after we break it down into little chunks, right? Run your code, and it should pass.
Final Solution
const lengthOfLongestSubstring = function(s) {
let start = 0;
let seeker = 0;
let set = new Set();
let counter = 0;
while (seeker < s.length ) {
if(!set.has(s.charAt(seeker))) {
set.add(s.charAt(seeker));
counter = Math.max(counter, set.size);
seeker++;
} else {
set.delete(s.charAt(start));
start++;
}
}
return counter
};
Conclusion
We made it through! Hurray!!!! Now wipe the sand out of your eyes, and let’s take a look at what we’ve learned with this problem. Thankfully our author was very nice and straightforward with this problem. We broke things down and moved through the problem with the grace of a determined camel 🐪 . We took what we observed, planned out our code, and identified a better data structure to use. Our code even reads pretty nicely as well. Nice job!
If you’d like to read more about Sets, give this a try, or watch some really great videos on breaking down this problem. Scroll to the bottom and use the links below. Thanks for reading my blog. I hope you learned something new, and Don’t be afraid to give me some claps!
- Happy Coding
Links:Terrible Whiteboard’s Solution(Javascript): https://www.youtube.com/watch?v=WKTgajDkVcANick White's Solition(Java): https://www.youtube.com/watch?v=3IETreEybaAfreeCodeCamp.org(Sets): https://www.youtube.com/watch?v=wl8u02IdVxoLearn more about here Sets(MDN Web Documents): https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/SetGive it a try on Leetcode: https://leetcode.com/
