Description
Find the maximum length of a contiguous substring with no repeated characters.
Solution
def length_of_longest_substring(s):
last = {}
left = best = 0
for right, char in enumerate(s):
left = max(left, last.get(char, -1)+1)
last[char] = right
best = max(best, right-left+1)
return bestExamples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
["abcaef"]- Output
5
bcaef contains five distinct characters.
Example 2
- Input
["aaaa"]- Output
1
Any second a would repeat.
Example 3
- Input
[""]- Output
0
An empty string has length zero.
Approach
Remember last positions and move the left boundary beyond a repeated character.
Time & space
O(n) expected time; O(min(n, alphabet size)) space. Here n is the input length.