Longest Substring Without Repeating Characters

Medium#3variable size

You get a string. Find the length of its longest piece of letters in a row where no letter repeats. Our example: "abcbdae" — the answer is 5, the piece "cbdae".

3 Longest Substring Without Repeating CharactersWalkthrough · 1×

Example: s = "abcbdae". Under the string is the map: letter and the last index it was seen at; faded entries point before left.

0a1b2c3b4d5a6elastc: i—
not reached yetwindowcurrent letterthe repeatleft the windowlongest piece

Start with an empty map: letter → the last index it was seen at

01/40
restart · back · play · step
Speed
1function lengthOfLongestSubstring(s):
2 last = empty map
3 left = 0
4 best = 0
5 for right from 0 to len(s) - 1:
6 c = s[right]
7 if c in last and last[c] >= left:
8 left = last[c] + 1
9 last[c] = right
10 best = max(best, right - left + 1)
11 return best
state
last
{}
left
–
right
–
c
–
best
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Any piece without repeats that ends at right can start no earlier than one past the last copy of s[right]. So left jumps straight there instead of stepping one letter at a time.
  2. The map is never cleaned, so it may hold a letter that has already left the window. The check last[c] ≥ left tells the two apart: a copy before left is no repeat, and left never moves back.
  3. The window has no repeats after every step, and each right is measured once, so the longest such piece is the best of these lengths.

Complexity

Time O(n): one pass, map lookups are O(1), and left only jumps forward. Memory O(k), where k is the number of different letters.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.