3. Longest Substring Without Repeating Character

All Hail the Mighty Set! His likeness knows no other… so no duplicates. Keep reading. You’ll get the joke. It’s pretty hip stuff, I promise. 😂 😆 😝

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.

🐫 Look at the determination in their eyes, Be like the camel, my friends! 🐫

The Prompt

My Thoughts

It’s all about the unique values! 🦆 🦆 🦆

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.

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.

The First example syncs up nicely with the prompt. We see the input, output, and why we get the return value.

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.

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.

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

Haboobs are no joke, neither is this leet code problem. 🏖 ⛈ 🐫

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

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.

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.

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.

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 …

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.

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 ++.

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 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 ++.

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

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

Career Changer, Software Engineer & Web Developer

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store