[python 刷题] 3 Longest Substring Without Repeating Characters

[python 刷题] 3 Longest Substring Without Repeating Characters

题目：

这到提要求找的是最长的，没有重复符号的子字符串

解题思路是用双指针+哈希表，左右指针指向子字符串的开始和结束的位置，哈希表存储每个字符串最后出现的下标+1，每次更新右侧指针时，如果当前字符是已经出现的字符，则将左指针移向最后出现的位置

最后更新一下最长子字符串的长度，按照案例过一遍：

开局的时候 dict 是空的，左右指针同时指向空

遇到没重复的字符串， r r r 指向下一个字符

b, c 没有遇到重复字符，所以持续更新 dict 和右侧指针位置:

这里存储的所有位置都是下标+1，主要是为了针对只出现 1 个字符的案例，如 " "，如果只是用 r − l r - l r−l，得出的结果就是 0 − 0 0 - 0 0−0，所以针对这个情况，所有存储的位置都是下标+1，计算字符串长度时也用 r − l + 1 r - l + 1 r−l+1 的方式补回

遇到了第二个 a:

这个时候左侧的指针从 0 移到了 1，res 的对比成了 res 与 3 − 1 + 1 3 - 1 + 1 3−1+1 的对比，自然长度还是一样的

这个时候同步更新 a 最后出现的坐标位置，移到下一个字符：

我标了一下，取值永远取的是 r r r 和 l l l 之间的这个字符串长度

另外关于 l l l 的取值也需要做一点额外的对比，如考虑下面这个情况：

如果取 b b b 之前所在的下标位置，依旧会取到包含重复字符的字符串，因此需要取当前 l l l 和 当前字符上一个下标中的最大值

代码如下：

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # use d to store the last appearance idx
        d = {}
        l, res = 0, 0

        for r, c in enumerate(s):
            l = max(l, d.get(c, 0))
            res = max(res, r - l + 1)
            print(res, l, r, c)
            d[c] = r + 1

        return res