Find the Length of the Longest Substring Without Repeating Characters (in JavaScript)

In this blog post we'll be exploring the solution to a potential interview question you might come across as a software engineer: how to find the length of the longest substring without repeating characters.

While you may not come across this question exactly the way it has been phrased here, the example we're using is a prime example of an interview question that can be approached and solved using the Sliding Window technique, a skill that's incredibly important to know when and how to use.

We'll also be working through the solution using JavaScript syntax.

Ready? Let's go!

The Problem

Let's first get a sense of the problem as we'd like to describe it:

Given a string, find the length of the longest substring without repeating characters.

As an example, let's say the following string was passed in as an argument:

"abcabcbb"

In this case, there would be two substrings of the same length ("abc" and "abc"), both of which have a length of 3. We're traversing through the string until we hit a repeat, in this case that's:

a b c a <-- repeat, end of substring

So "abc" is our substring, with a length of 3. That length of 3 is what we should be returning at the end of our function.

Sliding Window

The approach that we should use to tackle this problem is a Sliding Window technique, an approach that can help to shrink a potential solution with nested loops into one loop through a data set.

The two keys features of an algorithm that can be solved with a sliding window to try and spot are:

1. It features a data structure that is ordered and iterable (like an array or a string)
2. It usually asks for the result to be some kind of measurable subrange, like the "longest" or "shortest" of something

A third feature, like I mentioned above, is that there's usually a solution to the problem that involves brute forcing an answer, usually by nesting multiple loops through the data that results in a large runtime of O(n^2) or higher.

The core idea of a sliding window is that you're creating a "window" of two pointers over a subset of the data, that grows or shrinks as it iterates over the data set.

For instance, if we have an array of:

[1, 2, 3, 4, 5, 6]

And we had a "window" of 3 elements, we would move through the array looking at data as follows:

[1, 2, 3]
   [2, 3, 4]
      [3, 4, 5]
         [4, 5, 6]

Let's see how we can apply that to the problem we're working on right now.

The Solution

First of all, let's establish our function:

function lengthOfLongestSubstring(str) {

}

Now, since we know we're going to be using two pointers in a sliding window and we're going to be returning a max length value at the end of our function, let's establish those variables:

function lengthOfLongestSubstring(str) {
    let a_pointer = 0;
    let b_pointer = 0;
    let max = 0;
}

And last but not least, the final stage of our preparation for the core logic is creating an object that will hold our string characters as we iterate through the string. We know to use this because we know we need to be checking for the existence of duplicate values.

In this case, let's use a JavaScript Set() object, as that can simply hold a value with no need for a key/value pairing.

function lengthOfLongestSubstring(str) {
    let a_pointer = 0;
    let b_pointer = 0;
    let max = 0;

    let charSet = new Set();
}

It's time to get down to work!

The core logic of what we're doing can be broken down into two parts:

1. Check to see if the string character in the b_pointer position doesn't exist yet in our Set object. If not, we'll add that value to the set, increment the pointer to move to the next character (growing the size of the window), then update the max value with the current length of the Set (or keep it as is, if the max is less than the set value after the following step.)
2. If the string character in the b_pointer exists in the Set already, we know we've officially reached the end of a substring. We'll remove the character from the a_pointer position in the string from the set and increment the pointer, moving the window forward.

This can be represented in a loop like so:

function lengthOfLongestSubstring(str) {
    let a_pointer = 0;
    let b_pointer = 0;
    let max = 0;

    let charSet = new Set();

    while (b_pointer < str.length) {
        if (!charSet.has(str.charAt(b_pointer))) {
            charSet.add(str.charAt(b_pointer));
            b_pointer++;
            max = Math.max(charSet.size, max);
        } else {
            charSet.delete(str.charAt(a_pointer));
            a_pointer++;
        }
    }

    return max;

}

And we're done!

This solution works by moving the window through the string, only growing it by advancing the b_pointer until a duplicate value is found, while keeping the max variable at its highest ever value. If at any point b_pointer finds a duplicate then the back of the window moves up, only allowing b_pointer to move on again once the a_pointer has removed the first appearance of that character from the set so the loop may continue uninterrupted.

The trick to this particular solution is that we don't need to return the actual substring itself, but rather just the length of the longest uninterrupted section of the string between duplicates. We could find and return the substring itself if we wanted, but that would be a slightly different question (and a worthy stretch goal to revisit!)

If you've come this far, thanks very much for reading! I hope this has been helpful or valuable to you in any way as a resource for practicing and learning algorithms and data structures.

I'll continue to write more posts about problems and solutions as I work through them myself, so stay tuned!