Given a string s, find the length of the longest substring without duplicate characters.
A substring is a contiguous sequence of characters within a string.
Example 1:
Input: s = "zxyzxyz"
Output: 3 Explanation: The string "xyz" is the longest without duplicate characters.
Example 2:
Input: s = "xxxx"
Output: 1
Solution¶
The algorithm uses sliding window technique:
Right pointer (r) moves forward adding characters
If we find a duplicate, left pointer (l) moves forward removing characters until duplicate is gone
Track maximum length seen so far
Time Complexity: O(n)
Space Complexity: O(min(m,n))
In [1]:
def lengthOfLongestSubstring(s):
l=0
res=0
subs=set()
for r in range(len(s)):
while s[r] in subs:
subs.remove(s[l])
l+=1
subs.add(s[r])
res= max(res, len(subs))
return res
In [3]:
lengthOfLongestSubstring('abcabcbb')
Out[3]:
3