不重复子串最大值问题

问题描述

给定一个字符串 s，不包含空格字符，要求找出所有连续的子串中不包含重复字符的最大长度。例如，在字符串 "abcabcbb" 中，“abc” 就是一个满足条件的最长子串。

解题思路

滑动窗口法

此问题可以使用滑动窗口的方法来解决。滑动窗口的核心思想是维护一个当前子串，确保这个子串内的所有字符都是唯一的，并且尽量扩展它的长度。

步骤详解

1. 初始化：设定两个指针 left 和 right 分别表示滑动窗口的左右边界，初始时都位于字符串的起始位置。同时使用一个哈希集合来存储当前子串中已经出现过的字符。
2. 扩展右边界：移动 right 指针向右，每次将 s[right] 加入哈希集合。如果加入失败（即该字符已存在于集合中），则停止移动，并记录当前窗口的长度。
3. 收缩左边界：当发现重复字符时，需要逐步缩小滑动窗口以去除重复部分。此时从 left 开始，依次将集合中的元素移除，直到不包含重复字符为止。
4. 更新最大值：在每次移动 right 指针后，如果当前子串的长度大于已记录的最大值，则更新最大值。

示例

考虑字符串 "abcbb"：

• 初始状态: left = 0, right = 0, 集合为空。
• 右指针向右移动到字符 'a'，集合为 {'a'}。
• 右指针继续移动到字符 'b'，集合为 {'a', 'b'}。
• 右指针再移动到字符 'c'，集合为 {'a', 'b', 'c'}，此时 right 指向字符 'b' 时集合中已经有 'b'，需要收缩窗口。

具体步骤如下：

1. 当右指针指向 'd'（假设没有重复）：当前子串 "abc"。
2. 右指针继续移动至字符串结束或遇到重复字符时停止，并记录当前子串长度。

代码实现

def length_of_longest_substring(s):
    char_set = set()
    left = 0
    max_length = 0
    
    for right in range(len(s)):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        char_set.add(s[right])
        max_length = max(max_length, right - left + 1)
    
    return max_length

总结

使用滑动窗口的方法可以高效地解决不重复子串的最大值问题。这种方法通过动态调整窗口的左右边界，使得在遍历过程中始终保持窗口内的字符唯一性，并记录最大长度，从而找到满足条件的最长子串。