Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3.
This is a typical sliding window problem and this post will introduce different approaches from the brute force one to the sliding window step by step, and you will see the time complexity could be improved from O(n^3) to O(n^2) and finally to O(n).
Brute force – O(n^3) & O(n^2)
We can used a nested for-loop to search each substring starting with each letter. Checking whether the next letter is existed requires O(n), adding up to O(n^3). Or, we can maintain a hashset containing all letters for the current substring, so that time complexity for examining the new letter could be reduced to O(1).
Sliding window – O(n) with two passes
To improve that, we can use sliding windows. Using left and right as two pointers to scan the input string. With the hashset recoding the existing letters, once a repeated letter appears, we could move left until the repeated letter was removed.
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
cur = set([])
left = right = 0
ret = 0
while left < len(s) and right < len(s):
if s[right] not in cur:
cur.add(s[right])
right += 1
ret = max(ret,right-left)
else:
cur.remove(s[left])
left += 1
return ret
Sliding window – O(n) with one pass
However, we can achieve it with one pass only. Based on the sliding window mentioned above, we can maintain another hashmap to record the position for each existing letters. In this case, instead of move left letter by letter, we could jump to the next position of the repeated letter.
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
dic = {}
i = j = ret = 0
while j < len(s):
i = max(i,dic.get(s[j],-1)+1)
ret = max(ret,j-i+1)
dic[s[j]] = j
j += 1
return ret