3. 无重复字符的最长子串

https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

解法一：

用左开右闭区间(start, i]表示无重复串范围，start初始=-1，i一次遍历数组。用一个dict存储每个字符上一次出现位置k，若上次出现在start之后，说明发生重复，舍弃前面的部分，start=k。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        dict = [-1] * 256   #字符上次出现位置表
        start = -1
        maxLen = 0
        for i in range(len(s)):
            if dict[ord(s[i])] > start:
                start = dict[ord(s[i])]     #关键
            dict[ord(s[i])] = i     #更新
            maxLen = max(maxLen, i-start)
        return maxLen

解法二：滑动窗口模板

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        window={}
        left=0
        right=0
        maxLen = 0
        while right < len(s):
            c = s[right]
            right += 1
            window[c] = window.get(c, 0) + 1
            #重复次数大于1（说明有重复字符）就缩小窗口，直到不大于1为止
            while window[c] > 1:    
                d = s[left]
                left += 1
                window[d] -= 1
            #此时无重复，更新maxLen
            maxLen = max(maxLen, right-left)
        return maxLen