However, at O(n^2), this is way too inefficient. Let's determine a better solution. At a quick glance, we know we'll need to iterate and have some form of on-going storage for tracking purposes.

Solution to Longest Substring Without Duplicate Characters

Our optimized method solves the problem efficiently with respect to time, yet requires very little extra space. Remember the manual steps our brute force approach above? Oftentimes, efficient solutions just cut out steps from slower ones.

Consider the step by step we already did. I highlighted/bolded some steps we probably don't need:

1. First, we consider a. Longest max is 1.
2. Then, we look at al. Longest max is now 2.
3. We look at alg. It's now 3.
4. o - 4
5. d - 5
6. a - wait, we've seen this before. Max is still 5, and the next few steps are also invalid and won't change the max. 1. We have substring algodai - i - substring has duplicate, so invalid 1. algodail - l - substring has duplicate, so invalid 1. algodaily - y - substring has duplicate, so invalid
7. Now we can start from l, and repeat from step 1... (l, lg, etc.)

Notice something? The last 3 steps before we start from l could've been cut out! We knew that once we encountered the second a, all substrings that we extended to would be invalid. So why don't we jump straight to starting from l as soon as we see the duplicate?

That's the idea behind the optimal solution.

More Setup

To find the longest substring with no repeating characters, we'll read each character of the input string from left to right.

At the same time, we'll keep track of the current substring and the maximum substring length found so far. To keep track of the current substring, we'll record its starting index in a variable startInd and its last index in a variable i.

This solution uses an array, which has the same size as the size of the alphabet. The array stores the index of the character of the alphabet last found in the input string (in other words, it's tracking the last seen character element). In this tutorial, we call this array lastPos.

1const lastPos = [];

As we read the characters, we'll also maintain the lastPos array for storing the index of each character's last occurrence in the string. The lastPos array would be initialized to -1.

Suppose at index position i, we have read character x. Before that, we would've encountered this character at lastPos[x]. lastPos helps us remember where we last saw a duplicate character. That way, we can use lastPos[x] + 1 to "remove" the first duplicate from the current substring, and test against a valid substring.

Cases

There are two possible cases that are occurring, which are shown in the figure and explained below. For now, we'll assume that lastPos can be indexed by x. Later we'll discuss how to implement the indexing for this array.

These two cases help us make sense of when to start or stop consideration of the current substring.

1. Case 1: x has already occurred in the current substring. In this situation startInd <= lastPos[x].

   To handle this case, start a new substring after lastPos[x]-- to do this, we can do startInd = lastPos[x]+1. Update the length of the current substring as (i-startInd+1).

2. Case 2: x has either not occurred in the string or it has occurred in some previous substring. In this case, startInd > lastPos[x] and we can read the next character of the input string and keep updating length and maximum length found so far.