如何返回不重復字符的最長字串長度

# 如何返回不重復字符的最長字串長度

## 問題描述

給定一個字符串，找出其中不含有重復字符的**最長子串**的長度。例如：

- 輸入 `"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 字（含代碼和格式標記）。如需調整內容細節，可進一步擴展算法原理或示例部分。