不重复子串

什么是不重复子串？

在计算机科学中，“不重复子串”通常指一个字符串中的最长连续子串，其中所有字符都是独一无二的，没有重复出现的情况。例如，在字符串 "abcabcbb" 中，“abca” 和 “bca” 都是不重复子串，但它们都不是最长的。

问题背景

这个问题来源于编程面试和算法竞赛中，被广泛讨论的一个经典问题：“给定一个字符串 s，请找到其中包含不重复字符的最长子串长度。” 这个问题是 LeetCode 上第 3 题（LeetCode 3. Longest Substring Without Repeating Characters），也被其他在线平台多次提出。

解决方案

滑动窗口法

滑动窗口是一种常见的解决此类问题的方法。具体来说，我们可以使用两个指针 i 和 j 分别表示当前子串的起始位置和结束位置。同时利用一个哈希集合来存储当前子串中出现过的字符，确保这些字符都是独一无二的。

1. 初始化：设置 i = 0, j = 0，并创建一个空的哈希集合。
2. 遍历字符串 s：
   • 当 j 指针指向的新字符不在哈希集合中时，将其加入到集合中，并将 j 右移一位（即扩大子串长度）。
   • 如果新的字符在集合中已经存在，则从 i 开始逐个删除集合中的元素，直到新加入的字符不再出现为止。然后将 i 指针右移一位（即缩小当前子串长度），并将该字符加入到集合中。
3. 在遍历过程中，始终记录最长不重复子串的长度。

代码实现

下面是一个使用 Python 实现的例子：

def length_of_longest_substring(s: str) -> int:
    if not s:
        return 0
    
    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

这段代码中，我们定义了左右指针，并使用一个集合来存储当前窗口内的字符。当新加入的字符已经在集合中存在时，则不断移除左端点指向的字符并移动左指针，直到满足条件。

实际应用

这个问题不仅在编程竞赛中经常出现，在实际的数据分析和文本处理等场景中也有广泛的应用。例如，在股票价格序列中查找不存在重复的日子；或者在一个长篇文章中找到包含不同词汇的最大段落长度等等。

结果讨论

滑动窗口法的时间复杂度为 O(n)，其中 n 为字符串 s 的长度，因为每个字符最多只会被处理两次（一次加入集合，一次移除）。空间复杂度则取决于输入字符串中不同的字符数量。通过这种方法可以有效地找到不重复子串的最长长度，在实际应用中有很高的效率和实用性。

这个算法背后的逻辑简单而强大，展示了计算机科学中滑动窗口技术的灵活性和通用性，也让我们看到了如何将现实问题抽象为易于解决的形式。