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

题目

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

示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。

题解

思路：通过start存储不重复字符串的开始位置，res存储长度，cache字典存储遇到的字符及其位置。

1. 遍历字符串的字符与下标
2. 判断是否在cache中见过该字符。进行处理
3. 判断是否在cache中的该字符下标位置是否在start之后。进行处理
4. 更新start，当前字符串以及res

def lengthOfLongestSubstring(self, s: str) -> int:
        start, res, cache = 0, 0, dict()
        for idx, c in enumerate(s):
            if c in cache and cache[c] >= start:
                start = cache[c]+1
                cache[c] = idx
            else:
                cache[c] = idx
                res = max(res, res-start+1)
        return res

执行结果：通过
显示详情
执行用时 :60 ms, 在所有 Python3 提交中击败了94.19%的用户
内存消耗 :13.7 MB, 在所有 Python3 提交中击败了5.88%的用户