Interview challenge · medium · string, sliding-window, hash-set
Longest Substring Without Repeating Characters
El reto
El enunciado va en inglés, igual que en el vídeo.
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).
La solución
# 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