Longest Substring Without Repeating Characters#

Given a string, find the length of the longest contiguous substring that contains no repeated characters. Only substrings (unbroken runs of characters) count, not subsequences. Return that length.

Example#

Input: s = "abcabcbb" Output: 3, from the substring “abc”.

Input: s = "bbbbb" Output: 1, from the substring “b”.

Brute force#

Generate every substring and check each one for duplicate characters using a set, keeping the longest valid length. Enumerating all substrings is quadratic and checking each adds more work.

• Time: O(n^3) in the naive form, O(n^2) with careful checks.
• Space: O(n).

Optimal approach#

Slide a window with two pointers. Expand the right edge one character at a time and record each character’s most recent index in a map. When you hit a character already inside the window, jump the left edge to just past its previous occurrence, so the window stays duplicate-free. The answer is the largest window width seen.

Python solution#

 1def length_of_longest_substring(s):
 2    last_seen = {}
 3    left = 0
 4    best = 0
 5    for right, ch in enumerate(s):
 6        if ch in last_seen and last_seen[ch] >= left:
 7            left = last_seen[ch] + 1
 8        last_seen[ch] = right
 9        best = max(best, right - left + 1)
10    return best

Complexity#

• Time: O(n), each character enters and leaves the window once.
• Space: O(k), where k is the number of distinct characters.

This problem is the flagship sliding window technique question. Keep practicing with the 60-day challenge.