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

sliding window, https://leetcode.cn/problems/longest-substring-without-repeating-characters/

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

子字符串是字符串中连续的非空字符序列。

示例 1:

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

示例 2:

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

示例 3:

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

提示：

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

滑动窗口

是一个队列，比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！如何移动？我们只要把队列的左边的元素移出就行了，直到满足题目要求！

一直维持这样的队列，找出队列出现最长的长度时候！时间复杂度：O(n)

滑动窗口是一种常用的算法技巧，用于解决数组或字符串中的子数组或子字符串问题。在下面的代码中，滑动窗口的概念体现在通过移动两个指针（起始指针和结束指针）来维护一个当前的无重复子串。

滑动窗口的基本思想

初始化：
- 维护一个窗口 [start + 1, i]，表示当前的无重复子串。
- 使用一个字典 char_index 来记录每个字符最近一次出现的位置。
扩展窗口：
- 遍历字符串，逐个字符地扩展窗口的右边界 i。
收缩窗口：
- 如果当前字符 c 在字典中且其上次出现的位置在当前窗口内，则需要收缩窗口的左边界 start，使其不包含重复字符。

python

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 初始化变量
        start = -1  # 当前无重复子串的起始位置的前一个位置
        max_length = 0  # 最长无重复子串的长度
        char_index = {}  # 字典，记录每个字符最近一次出现的位置
        
        # 遍历字符串
        for i, char in enumerate(s):
            # 如果字符在字典中且上次出现的位置大于当前无重复子串的起始位置
            if char in char_index and char_index[char] > start:
                # 更新起始位置为该字符上次出现的位置
                start = char_index[char]
            
            # 更新字典中字符的位置
            char_index[char] = i
            
            # 计算当前无重复子串的长度，并更新最大长度
            current_length = i - start
            max_length = max(max_length, current_length)
        
        return max_length

代码解读
k：记录当前无重复子串的起始位置的前一个位置，初始值为 -1。
res：记录最长无重复子串的长度，初始值为 0。
c_dict：一个字典，用于记录每个字符最近一次出现的位置。
处理字符
python
            if c in c_dict and c_dict[c] > k:  # 字符c在字典中 且 上次出现的下标大于当前长度的起始下标
                k = c_dict[c]
                c_dict[c] = i
            else:
                c_dict[c] = i
                res = max(res, i - k)
条件判断：
if c in c_dict and c_dict[c] > k：检查当前字符 c 是否在字典中，并且该字符上次出现的位置是否大于当前无重复子串的起始位置的前一个位置 k。
如果条件成立，说明当前字符 c 在之前的子串中已经出现过，且该位置在当前无重复子串的范围内，因此需要更新 k 为该字符上次出现的位置。
k = c_dict[c]：更新 k 为字符 c 上次出现的位置。
c_dict[c] = i：更新字典中字符 c 的位置为当前索引 i。
否则：
c_dict[c] = i：更新字典中字符 c 的位置为当前索引 i。
res = max(res, i - k)：计算当前无重复子串的长度 i - k，并更新 res 为当前最大值。

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

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