-->

Sunday, February 25, 2024

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
'''

No comments:

Post a Comment