最长不重复子字符串

这是Leetcode第三题，难度中等。题目如下：

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

示例 1:

​ 输入: s = “abcabcbb”
​ 输出: 3
​ 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:

​ 输入: s = “bbbbb”
​ 输出: 1
​ 解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:

​ 输入: s = “pwwkew”
​ 输出: 3
​ 解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
​ 请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。
示例 4:

​ 输入: s = “”
​ 输出: 0

提示：

​ 0 <= s.length <= 5 * 104
​ s 由英文字母、数字、符号和空格组成

思路没啥好说的，就是滑动窗口，只不过我是个笨比，我用了大概十几个小时的时间看了好几个视频才把这玩意儿给捋顺了。主要参考：https://b23.tv/BV1r7411X7mJ

这里我打算从答案反过去做记录理解。为了更便于理解，用了很长的变量名称。

class Solution:
    def longestNoRepetSubString(self, s: str) -> int:
        cur_sub_str_start_index, res_longest, appeared_str_dict = 0, 0, {}
        for sub_str_end_index, sub_s in enumerate(s):
            if sub_s in appeared_str_dict and appeared_str_dict[sub_s] >= cur_sub_str_start_index:
                cur_sub_str_start_index = appeared_str_dict[sub_s] + 1
                appeared_str_dict[sub_s] = sub_str_end_index
            else:
                appeared_str_dict[sub_s] = sub_str_end_index
                cur_string_length = sub_str_end_index - cur_sub_str_start_index + 1
                res_longest = max(res_longest, cur_string_length)

        return res_longest

解释下出现最重要的几个变量及其作用：

说明之前先解释下enumerate(s)：

enumerate(iterable, start=0)

返回一个枚举对象。iterable 必须是一个序列、一个迭代器，或者其它某种支持迭代的对象。enumerate()返回的迭代器的__next__()方法返回一个元组，该元组包含一个计数（从start开始，默认为0）和迭代iterable得到的值。

举个例子enumerate("abcdef")，其返回结果是一个对象，将其循环取出之后为：

>>> for index, s in enumerate(“abcabcbb”):
… print(index, s)
…
0 a
1 b
2 c
3 a
4 b
5 c
6 b
2 b

也就是字符串中的每个字符都有了”index”

  • cur_sub_str_start_index：当前子字符串起始索引，还有一个结束索引，这两个索引构成一个完整的子字符串
  • res_longest：最长不重复子字符串长度
  • appeared_str_dict：出现过的字符上次出现位置的字典。其值的形式为{'a': 0, 'b': 1, 'c': 2}

下面是其实现逻辑：

循环字符串及其index，这个index同时是一个子串的结束索引。以上述为例，index为2时，已出现字符字典为：{'a': 0, 'b': 1, 'c': 2}，子字符串长度为结束位置index - 起始位置index + 1 也即 2-0+1=3，也即目前最长子字符串长度为3，res_longest = cur_string_length = 3

当等于3时，a已经出现过，那么就需要设定新的子字符串的起点也就是cur_sub_str_start_index，设定的位置就是a上次出现的位置的下一个字符，也就是appeared_str_dict[sub_s] + 1,这是这个算法最关键的部分。我在这里绕了许久。理解了这一跳，这个算法也就清晰了。

换个例子，比如：acbdbefgn

从左到右一个个看过去，到第二个b的时候出现了重复，此时第一个不重复子串acbd已经确定，那第二个子串从哪里开始呢，无论从c还是b都不符合条件的要么有重复要么没有abcd长，于是从b的下一个字母也就是d开始既没有重复，由于后续位置还没固定（可能更长的不重复字符串）也有可能满足条件，所以b的下一个位置作为第二个子串起点继续往下循环直到结束。

其他部分就简单了，循环更新当前子字符串长度，同时和上一个（也就是res_longest）长度比较，如果更长就更新结果，如果不是就继续循环，直到结束。