30 lines
973 B
Python
30 lines
973 B
Python
|
# Time: O(N)
|
||
|
|
# Space: O(N)
|
||
|
|
class Solution:
|
||
|
|
def lengthOfLongestSubstring(self, s: str) -> int:
|
||
|
|
'''
|
||
|
|
Sliding-window approach
|
||
|
|
'''
|
||
|
|
|
||
|
|
# Keep a track of unique chars we've seen so far in the substring
|
||
|
|
# we are looking at
|
||
|
|
seen = set()
|
||
|
|
start, end = 0, 0
|
||
|
|
maxl = 0
|
||
|
|
|
||
|
|
while start <= end < len(s):
|
||
|
|
# Our current substring is denoted by their bounds [start, end]
|
||
|
|
# If we see a char in `end` which is already seen by us, we need
|
||
|
|
# to keep moving `start` until we are left with a new character
|
||
|
|
while s[end] in seen:
|
||
|
|
# Since `start` is moving up, we need to remove existing
|
||
|
|
# `start` char from the set if it exists
|
||
|
|
seen.remove(s[start])
|
||
|
|
start += 1
|
||
|
|
|
||
|
|
seen.add(s[end])
|
||
|
|
maxl = max(maxl, (end - start) + 1)
|
||
|
|
end += 1
|
||
|
|
|
||
|
|
return maxl
|