Sliding window · Variable size

Medium · O(n) time · O(min(n, m)) space

Problem

Given a string s, return the length of the longest substring that has no repeated character. A substring is a run of neighbouring characters, so you can't skip any.
Example 1 Input: s = "abcabcbb" Output: 3 ("abc") Example 2 Input: s = "pwwkew" Output: 3 ("wke"; "pwke" is a subsequence, not a substring) Example 3 Input: s = "bbbbb" Output: 1 ("b")
Constraints 0 ≤ s.length ≤ 5 × 10^4 s holds letters, digits, symbols and spaces

Brute force

Take a string. Look for a stretch of neighbouring letters where no letter appears twice. How long can such a stretch be?

  1. The stretch must be unbroken: you cannot skip letters (that would be a subsequence, not a substring).
  2. No letter may appear twice inside it.
  3. Return the length of the longest one. We do not need the stretch itself.

A stretch is described by its two ends. Here are two stretches of "pwwkew": one is fine, and one has a repeated letter.

One fact helps: if a stretch has a repeated letter, any longer stretch that contains it has the repeat too.

The direct idea: try every start, extend it one letter at a time, and stop at the first repeat.

The problem with it

There are n starting points, and each can extend up to n letters, with a set lookup at every step. That is about n × n steps. For 50,000 letters it is over a billion.

It also wastes work. In "pwwkew", the start at 1 fails at index 2. The start at 2 then reads the letter "w" again and goes on. All the work from index 2 onwards that the first start did is thrown away and done again.

How to think your way to the optimal solution

When a repeat appears, we do not need to start from scratch. Can we keep the part of the stretch that is still good, and only drop what is broken?

Think of a window sliding along the string. We keep one stretch, called the window, and walk its right edge across the string one letter at a time. For each new letter:

Why drop from the left only? Once the new letter repeats an earlier one, any stretch that holds both copies can never be valid again, however far right it grows. So the earlier copy must leave, and so must everything to its left. And we stop the moment the repeat is gone, because dropping more would only shrink a window that is already valid.

Each letter enters the window once and leaves at most once, so we never redo work.

The optimal solution

  1. Start with an empty window (left = 0), an empty set seen, and best = 0.
  2. Move right across the string, one letter at a time.
  3. s[right] is in seen⟶remove s[left] from seen, left += 1, and check again
  4. s[right] is not in seen⟶add it to seen
  5. Set best = max(best, right − left + 1). After the last letter, return best.

By hand, on "pwwkew":

  1. p: not in the window. Window "p", best 1.
  2. w: not in the window. Window "pw", best 2.
  3. w (second): already in the window. Drop p, still there. Drop w, now it is gone. Add the new w. Window "w", best stays 2.
  4. k: add it. Window "wk", best 2.
  5. e: add it. Window "wke", best 3.
  6. w (third): already in the window. Drop w, then it is gone. Add the new w. Window "kew", best stays 3.

The answer is 3. Press Play to watch the window grow and shrink. The input "abba" is a good one to try. At the last a, the loop does not run at all, because the first a already left the window when the two bs collided.

Complexity analysis

O(n)
Time. Here's why: right moves forward n times. left only moves forward too, and it can never pass right, so it moves at most n times in total. Every step does a fixed amount of work. That is at most 2n steps.
O(min(n, m))
Space. The set holds only the letters in the window. A window cannot hold more letters than the string has (n), nor more different letters than the alphabet has (m).

Interviewer follow-ups

These are the questions that usually come next. Open one to see an answer you could say out loud.

"Return the longest substring itself, not only its length."

What they are checkingWhether you can carry a position along with a number. It is a small change, and a good check that you understand what left and right mean.

A strong answerWhenever best improves, I also save the current left. At the end, the answer is s[best_left : best_left + best]. The window never changes, only what I record.

"Allow up to k different letters, instead of none repeated."

What they are checkingWhether you see which part of your solution is the actual rule, so you can change it. This is the well-known "at most k distinct characters".

A strong answerThe window idea stays the same. The only thing that changes is when the window is broken: it is broken when it holds more than k different letters, instead of when a letter repeats. A set is no longer enough, because I must know when the last copy of a letter leaves. So I use a map from each letter to how many times it is in the window, and I drop from the left until the number of different letters is k or fewer.

"The string can contain any Unicode characters, and it arrives as a stream."

What they are checkingWhether your solution depends on hidden assumptions about the input, such as a small alphabet.

A strong answerA set or map handles any character, so Unicode is fine. I would avoid a fixed 128-slot array, because it assumes plain ASCII. For a stream, the window only needs the letters currently inside it, so I do not need the whole string. But in the worst case the window can be as long as the number of different characters in the alphabet, so memory is bounded by that, not by the stream length.

Spot this pattern