Interview challenge · medium · string, sliding-window, hash-set
Longest Substring Without Repeating Characters
The challenge
Given a string s, find the length of the longest substring (contiguous) that has no repeated characters.
Example
"abcabcbb" -> 3 ("abc")
"bbbbb" -> 1 ("b")
"pwwkew" -> 3 ("wke"; "pwke" is not contiguous)
"" -> 0Idea: sliding window. Keep a window with no repeats and remember the last index of every character. When the next character is already inside the window, jump the start right past its previous occurrence. Every character enters and leaves the window once: time O(n), space O(alphabet).
The solution
# Longest Substring w/o Repeats - ayotl.dev
def longest(s):
# sliding window: s[start:i] has
# no repeats; last = where we saw c
last, start, best = {}, 0, 0
for i, c in enumerate(s):
if last.get(c, -1) >= start:
# c repeats: jump past it
start = last[c] + 1
last[c] = i
best = max(best, i - start + 1)
return best
tests = ["abcabcbb", "bbbbb", "pwwkew", ""]
for s in tests:
print(f'"{s}" -> {longest(s)}')
$ python3 longest_substring.py
"abcabcbb" -> 3
"bbbbb" -> 1
"pwwkew" -> 3
"" -> 0