Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without repeating characters.

Example:

Input: s = "abcaechh"

Output: 3

Input: s = "ccccc"

Output: 1

Solution:

class Solution:

def lengthOfLongestSubstring(self, s: str) -> int:

if not s:

return 0

result = 1

lastseen = {}

left = 0

start, end = 0, 0

for i in range(len(s)):

if s[i] in lastseen and lastseen[s[i]] >= start: #aabba a->1 stays in lastseen

result = max(result, end - start + 1)

start = lastseen[s[i]] + 1

end = i

lastseen[s[i]] = i

return max(result, end - start + 1)

'''

O(N),

O(1) map can only have 256 (extended ASCII) elements maximum

'''