题目
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.
Constraints:
0 <= s.length <= 5 * 10^4
s
consists of English letters, digits, symbols and spaces.
思路
双指针,遍历字符串,用一个字典存储每个字符的最新位置,且每次遍历时保存最长长度。当当前字符在字典中且位置小于等于左指针所在的位置时,左指针跳至字典位置进一的位置,表示新的不重复字符串,直至遍历结束。
代码
python版本:
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
used_chars={}
max_count=0
l=0
for i,char in enumerate(s):
if char in used_chars and used_chars[char]>=l:
l=used_chars[char]+1
else:
max_count=max(max_count,i-l+1)
used_chars[char]=i
return max_count