[python 刷题] 3 Longest Substring Without Repeating Characters

[python 刷题] 3 Longest Substring Without Repeating Characters

题目：

Given a string s, find the length of the longest substring without repeating characters.

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

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

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

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

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

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

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

遇到了第二个 a:

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

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

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

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

如果取 $b$ 之前所在的下标位置，依旧会取到包含重复字符的字符串，因此需要取当前 $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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15