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.
當(dāng)我們看到重復(fù)項時辙浑，我們可以使用dict / hashtable更新每個元素的索引并更新滑動窗口的起點功氨。然后我們可以返回窗口長度的最大值暂论。
