Given a string s, find the length of the longest substring without repeating characters.
Example 1:
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
Example 4:
Input: s = ""
Output: 0
Constraints:
- 0 <= s.length <= 5 * 104
- s consists of English letters, digits, symbols and spaces.
Solution:
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
start = -1
seen = {} # stores index of each element we've seen
length = 0
for i in range(len(s)):
if s[i] in seen and seen[s[i]] > start: # e.g. "tmmzuxt" we don't want to calculate the first "t" "t"
start = seen[s[i]] # when we meet the 2nd "t" as the start point moved to 1st "m" already
seen[s[i]] = i
else:
seen[s[i]] = i
length = max(length, i - start) # we only need to calculate max length when new element comes in
return length # as if we see dup elements we will start from somewhere in middle
# where length will not go larger
We can use dict/hashtable to update the index of each element and update the start point of sliding window when we see duplicates. Then we can return the max of the length of the window.
当我们看到重复项时，我们可以使用dict / hashtable更新每个元素的索引并更新滑动窗口的起点。然后我们可以返回窗口长度的最大值。
