Find the Length of the Longest Substring Without Repeating Characters (in JavaScript)
Tags: javascript, algorithms, tutorial, leetcode
Published: 2020-08-13 00:19:41

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](https://stackoverflow.com/questions/8269916/what-is-sliding-window-algorithm-examples), 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](https://stackoverflow.com/questions/8269916/what-is-sliding-window-algorithm-examples), 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:

``` javascript
[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:

``` javascript
[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:

``` javascript
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:

``` javascript
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.

``` javascript
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:

``` javascript
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!