如何求无重复字符的最长子串的长度？

问题分析

本题要求在给定的字符串 s 里找出不包含重复字符的最长子串的长度。这里需要明确子串和子序列的区别，子串是字符串中连续的字符序列，而子序列可以是不连续的。例如，对于字符串 "abcabcbb"，"abc" 是子串，而 "acb" 就是子序列。

解题思路 - 滑动窗口法

滑动窗口是一种常用于处理数组或字符串中连续子序列问题的高效算法技巧。我们可以把它想象成一个在字符串上“滑动”的窗口，这个窗口的大小和位置可以动态变化。下面详细解释使用滑动窗口解决此问题的步骤：

1. 初始化窗口

我们需要两个指针，left 和 right，它们分别代表滑动窗口的左右边界。初始时，这两个指针都指向字符串的起始位置，也就是索引为 0 的地方。此时，窗口的大小为 1，只包含字符串的第一个字符。

我们还需要一个哈希表（在 Python 中用字典表示），用于记录每个字符最后一次出现的位置。这样，当我们遇到重复字符时，就能快速知道它上一次出现的位置。

2. 移动右指针

我们开始移动右指针 right，每移动一次，就把新字符加入到窗口中。右指针的移动就像是在不断扩大窗口的范围，尝试包含更多的字符。

3. 处理重复字符

在移动右指针的过程中，如果遇到了一个已经在哈希表中出现过的字符，并且这个字符上一次出现的位置在当前窗口内，那么就说明窗口内出现了重复字符。为了保证窗口内的字符不重复，我们需要移动左指针 left。具体来说，把左指针移动到该字符上一次出现位置的下一个位置，这样就能把重复字符排除在窗口之外。

4. 更新最长子串长度

在移动左右指针的过程中，我们会不断计算当前窗口的长度（即 right - left + 1），并与之前记录的最长子串长度进行比较。如果当前窗口的长度更长，就更新最长子串的长度。

5. 继续移动

重复步骤 2 - 4，直到右指针遍历完整个字符串。最后得到的最长子串长度就是我们要的答案。

代码实现步骤

下面是使用 Python 实现的代码，其中包含详细的注释：

def length_of_longest_substring(s: str) -> int:
    # 初始化一个字典，用于记录每个字符最后一次出现的位置
    char_index_map = {}
    # 初始化左指针，初始位置为 0
    left = 0
    # 初始化最长子串的长度，初始值为 0
    max_length = 0

    # 遍历字符串，右指针 right 从 0 开始
    for right in range(len(s)):
        # 获取当前右指针指向的字符
        char = s[right]
        # 如果字符已经在字典中，并且其最后一次出现的位置在当前窗口内
        if char in char_index_map and char_index_map[char] >= left:
            # 移动左指针到该字符最后一次出现位置的下一个位置
            left = char_index_map[char] + 1
        # 更新字符最后一次出现的位置
        char_index_map[char] = right
        # 计算当前窗口的长度
        current_length = right - left + 1
        # 更新最长子串的长度
        max_length = max(max_length, current_length)

    # 返回最长子串的长度
    return max_length

# 示例测试
s1 = "abcabcbb"
print(length_of_longest_substring(s1))  # 输出: 3

s2 = "bbbbb"
print(length_of_longest_substring(s2))  # 输出: 1

s3 = "pwwkew"
print(length_of_longest_substring(s3))  # 输出: 3    

复杂度分析

• 时间复杂度：，其中 是字符串的长度。我们只需要遍历一次字符串，每个字符最多被访问两次（一次是右指针移动时，一次是左指针移动时）。
• 空间复杂度：，其中 是字符集的大小。在本题中，字符集是英文字母、数字、符号和空格，因此 是一个常数。

通过上述的详细分析和代码实现，我们可以高效地解决无重复字符的最长子串问题。对于初学者来说，理解滑动窗口的思想可能需要一些时间和练习，但掌握了这种方法后，就能轻松解决很多类似的问题。