Longest Substring Without Repeating Characters

The problem

You are given a string text. Find the longest substring in which no character appears twice, and return its length. A substring is a run of characters that sit next to each other in text.

Example 1

Input: text = "abcbdab"

Output: 4

“cbda” has four different characters. Every longer substring repeats a character.

text

a0b1c2b3d4a5b6

Example 2

Input: text = "zzzz"

Output: 1

Any two characters next to each other are the same, so the best is a single “z”.

Example 3

Input: text = ""

Output: 0

The empty string has no characters at all.

Constraints

• 0 ≤ n ≤ 50,000, where n is the length of text
• text holds English letters, digits, symbols and spaces. Below, m is the number of different characters that can appear (under 100 here).

Clarifying questions

Substring or subsequence?

Substring. The characters must sit next to each other. We cannot skip any.

Do uppercase and lowercase count as different?

Yes. "a" and "A" are different characters.

Do spaces count?

Yes. A space is a character like any other, so " " has an answer of 1.

Do we return the substring or its length?

Only the length.

Spot the pattern

We want the longest contiguous run that obeys a rule (“no repeats”). And if a run breaks the rule, every longer run around it breaks it too. That is the sliding window pattern: grow the window on the right, and shrink it from the left only as much as needed to make it valid again.

Solutions

Brute forceO(n²)Sliding windowO(n)

Show all

This problem has two approaches. Checking every substring separately would be O(n³), which is just a slower brute force.

Brute force O(n²)

The idea

Try every start position i. From there, add characters one by one into a set. As soon as a character is already in the set, stop: every longer substring from i would contain that repeat too. The length just before the stop is the best for this start. Keep the best over all starts.

It is correct, but each start rebuilds almost the same set as the start before it.

Walkthrough

text

a0b1c2b3d4a5b6

best

0

1. best = 0
2. for i in range(len(text)):
3. seen = set()
4. for j in range(i, len(text)):
5. if text[j] in seen:
6. break
7. seen.add(text[j])
8. best = max(best, j - i + 1)
9. return best

For each start i, grow the substring to the right until a character repeats.

← BackStep →Play1 / 9

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Brute force: from every start, grow until a character repeats.
    // n starts, each growing up to n steps, so O(n^2) time. The set holds up to m characters.
    public int lengthOfLongestSubstring(String text) {
        int textLength = text.length();
        int best = 0;
        for (int i = 0; i < textLength; i++) {
            Set<Character> seen = new HashSet<>();
            for (int j = i; j < textLength; j++) {
                // Any longer substring from i would contain this repeat too.
                if (seen.contains(text.charAt(j))) break;
                seen.add(text.charAt(j));
                best = Math.max(best, j - i + 1);
            }
        }
        return best;
    }
}

Big O

Time O(n²)Space O(m)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The lit lines check one character, add it to the set and update the best. They sit inside two loops. A set lookup and a set add take one step on average, so each run is 1 step.

   1. best = 0
   2. for i in range(len(text)):
   3. seen = set()
   4. for j in range(i, len(text)):
   5. if text[j] in seen:
   6. break
   7. seen.add(text[j])
   8. best = max(best, j - i + 1)
   9. return best

2. 2 Count the runs on Example 1

   Example 1 has 7 characters. The table counts the inner runs for each start, including the run that finds the repeat and breaks.

   4 + 3 + 5 + 4 + 3 + 2 + 1 = 22 runs.

   start i	0	1	2	3	4	5	6
   inner runs	4	3	5	4	3	2	1

   total

   4 + 3 + 5 + 4 + 3 + 2 + 1 = 22

3. 3 Write the count for any n

   The worst case is a string with no repeats at all. Then start i runs to the very end:

   n + (n − 1) + … + 1 = n × (n + 1) / 2 = ½n² + ½n

   Check it with Example 1: a 7-character string with no repeats would take 7 × 8 / 2 = 28 runs. The real 22 is lower because repeats stop some starts early.

4. 4 Keep only the part that grows fastest

   • Drop the +½n and drop the ½. Neither changes how fast the count grows.

   What is left is n². One honest note: a substring with no repeats is at most m long, so the inner loop stops within m + 1 runs. That makes it O(n · m) in practice. With a big alphabet, that is still n².

   So the time is O(n²).

5. S Space: count the extra memory the same way

   The set holds the characters of one substring, so at most m of them. The space is O(m), which is at most O(n).

   seen (up to m characters)bestij

Sliding window O(n)

The idea

Keep a window, from left to right, that always holds distinct characters. A set holds what is inside the window.

Move right one step at a time. If the new character is already in the window, shrink the window from the left, one character at a time, until that character has left. Then add the new character and measure the window.

We never move left backward. Here is why that is safe: any window that starts further left and ends at right would contain the repeat, so it can never be valid.

The invariant: after each step, the window is the longest substring with no repeats that ends at right.

Walkthrough

text

a0b1c2b3d4a5b6

seen

empty

best

0

1. seen = set()
2. left = best = 0
3. for right in range(len(text)):
4. while text[right] in seen:
5. seen.remove(text[left])
6. left += 1
7. seen.add(text[right])
8. best = max(best, right - left + 1)
9. return best

The window from left to right always holds distinct characters. A set holds what is inside it.

← BackStep →Play1 / 13

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Sliding window: the window left..right always holds distinct characters.
    // Each character enters once and leaves at most once, so O(n) time.
    public int lengthOfLongestSubstring(String text) {
        Set<Character> seen = new HashSet<>();
        int left = 0, best = 0;
        for (int right = 0; right < text.length(); right++) {
            // Shrink from the left until the new character is no longer inside.
            while (seen.contains(text.charAt(right))) {
                seen.remove(text.charAt(left));
                left++;
            }
            seen.add(text.charAt(right));
            best = Math.max(best, right - left + 1);
        }
        return best;
    }
}

Big O

Time O(n)Space O(m)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   Two kinds of work repeat. Each run of the for loop adds one character. Each run of the inner while loop removes one character. Both are 1 step. The while sits inside the for, so the question is how often it really runs in total.

   1. seen = set()
   2. left = best = 0
   3. for right in range(len(text)):
   4. while text[right] in seen:
   5. seen.remove(text[left])
   6. left += 1
   7. seen.add(text[right])
   8. best = max(best, right - left + 1)
   9. return best

2. 2 Count the runs on Example 1

   Example 1 has 7 characters. right moves 7 times, adding each character once. left moves 4 times in total: twice at the first repeated “b”, and twice at the last “b”.

   7 + 4 = 11 runs.

   pointer	right (adds)	left (removes)
   moves on Example 1	7	4

   total

   7 + 4 = 11

3. 3 Write the count for any n

   right moves n times. left only moves forward and never passes right, so across the whole run it moves at most n times:

   n (adds) + at most n (removes) ≤ 2n

   Check it with Example 1: 11 runs, below 2 × 7 = 14.

4. 4 Keep only the part that grows fastest

   Drop the 2. Two passes of pointers do not change how the work grows. What is left is n, even with a loop inside a loop.

   So the time is O(n).

5. S Space: count the extra memory the same way

   The set holds the window’s characters, and the window has no repeats. So it holds at most m characters. The space is O(m).

   seen (up to m characters)leftrightbest

Common mistake

Resetting the window instead of shrinking it

When a repeat comes in, it is tempting to empty the set and restart the window at right. That loses good characters. In “dvdf”, restarting at the second “d” throws away “v” and finds only “df”, but the answer is “vdf”. Shrink from the left only until the repeat is gone.

Tested at the limits

2,000 random texts of 0 to 10 characters from a, b and a space, so repeats are close together and the empty text comes up too. The brute force and the sliding window gave the same answer every time.

Largest inputs	Result
50,000 characters (the most allowed): all 95 printable characters, over and over, so every new character pushes one out. Sliding window.	0.01 s, and about 0.01 MB of extra memory: the set never holds more than 95 characters, which is the O(m) space.
50,000 characters, same text. Brute force.	0.5 s, about 70 times slower. It runs at full size only because each start stops after 96 steps here.