题目描述

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

样例

输入: "abcabcbb"
输出: 3 

输入: "bbbbb"
输出: 1

输入: "pwwkew"
输出: 3

算法1

双指针 $O(N)$

[start,ed]区间维护无重复字符的区间，字典h记录每个字符出现的位置
当遍历到一个出现在前面区间的字符时，更新start。

时间复杂度 O(N)

python 代码

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        ans = 0

        n = len(s)
        h = {}
        start = 0 
        for ed in range(0,n):
            if s[ed] in h:  #当前字符str[ed] 出现在[start,ed-1] 中
                start = max(start,h[s[ed]] +1)  # start在重复字符的后面，那么无关紧要，如果在前面，那么start需要跳过重复字符
            ans = max(ans,ed-start+1)  # 更新答案
            h[s[ed]]  = ed  # 更新重复字符的位置
        return ans