如何返回不重复字符的最长字串长度

# 如何返回不重复字符的最长字串长度

## 问题描述

给定一个字符串，找出其中不含有重复字符的**最长子串**的长度。例如：

- 输入 `"abcabcbb"`，输出 `3`（最长子串是 `"abc"`）
- 输入 `"bbbbb"`，输出 `1`（最长子串是 `"b"`）
- 输入 `"pwwkew"`，输出 `3`（最长子串是 `"wke"`）

## 解决方案

### 方法一：滑动窗口（双指针）

这是解决该问题的经典方法，时间复杂度为 O(n)，空间复杂度为 O(min(m, n))，其中 m 是字符集大小。

#### 算法步骤

1. 初始化两个指针 `left` 和 `right`，表示当前窗口的左右边界。
2. 使用一个哈希集合（或字典）记录当前窗口中的字符。
3. 移动 `right` 指针，扩展窗口：
   - 如果当前字符不在集合中，加入集合并更新最大长度。
   - 如果字符已存在，移动 `left` 指针，直到重复字符被移除。
4. 重复直到 `right` 指针遍历完整个字符串。

#### Python 实现

```python
def length_of_longest_substring(s: str) -> int:
    char_set = set()
    left = 0
    max_len = 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_len = max(max_len, right - left + 1)
    
    return max_len

方法二：优化滑动窗口（跳跃式移动）

当发现重复字符时，可以直接将 left 指针跳到重复字符的下一个位置，而无需逐步移动。

优化点

• 用字典记录字符的最新出现位置。
• 发现重复时，直接更新 left 到 max(left, 重复字符的下一个位置)。

Python 实现

def length_of_longest_substring(s: str) -> int:
    char_index = {}
    left = 0
    max_len = 0
    
    for right in range(len(s)):
        if s[right] in char_index:
            left = max(left, char_index[s[right]] + 1)
        char_index[s[right]] = right
        max_len = max(max_len, right - left + 1)
    
    return max_len

方法三：固定字符集的数组优化

如果字符集较小（如 ASCII 码），可以用固定大小的数组代替哈希表，进一步优化空间。

实现代码

def length_of_longest_substring(s: str) -> int:
    last_index = [-1] * 128  # ASCII 范围
    left = 0
    max_len = 0
    
    for right in range(len(s)):
        char = s[right]
        left = max(left, last_index[ord(char)] + 1)
        last_index[ord(char)] = right
        max_len = max(max_len, right - left + 1)
    
    return max_len

复杂度分析

边界条件与测试案例

测试案例

1. 空字符串："" → 0
2. 全重复字符："aaaa" → 1
3. 无重复字符："abcd" → 4
4. 混合情况："aababcbb" → 3

注意事项

• 需处理 Unicode 字符（方法一、二通用）。
• 输入为空时的返回值应为 0。

实际应用场景

1. 数据去重：统计文本中最长无重复片段。
2. 密码学：分析密钥的重复模式。
3. 生物信息学：寻找DNA序列中的独特片段。

总结

通过滑动窗口及其优化版本，可以高效解决最长无重复子串问题。推荐优先使用优化滑动窗口（方法二），兼顾可读性与性能。对于已知字符集的问题（如纯ASCII），可尝试数组优化（方法三）以进一步提升效率。

扩展思考

• 如果要求输出最长子串本身，如何修改代码？
• 如何处理流式数据（无法预知全部输入）的情况？

”`

注：实际字数约为 950 字（含代码和格式标记）。如需调整内容细节，可进一步扩展算法原理或示例部分。