[LeetCode解題攻略] 3. Longest Substring Without Repeating ...

題目描述

給定一個字串 s，請找出其中不含重複字母的最長子字串的長度。

• 輸入：s = "abcabcbb"
  輸出：3（最長的不重複子字串是 "abc"，其長度為 3）
• 輸入：s = "bbbbb"
  輸出：1（最長的不重複子字串是 "b"，其長度為 1）
• 輸入：s = "pwwkew"
  輸出：1（最長的不重複子字串是 "wke"，其長度為 3）

解題思路

此題的目標是找出字串中不含重複字母的最長子字串的長度，重點在於找到每個子字串，並確保子字串內部沒有重複的字母。這裡我們可以運用滑動窗口來解題。

滑動窗口是一種雙指針技術，適合用來處理連續區間的問題。我們會使用一個滑動窗口遍歷字串，用一個集合儲存目前窗口中的字符，並且保持窗口內的字符唯一性。

解法一：滑動窗口 + 集合

步驟：

1. 用 left 和 right 指針來控制窗口，初始時都指向字串開頭。
2. 用一個集合 char_set 存儲當前窗口內的字符。
3. 當 right 指向的字符不在 char_set 時，將其加入集合，並更新最大長度。
4. 當 right 指向的字符在 char_set 中時，從 left 開始移除字符直到窗口內字符唯一。
5. right 每次迭代右移，直到遍歷完整個字串。

這樣可以確保每次新增字符到窗口時，窗口內的字符都不重複。

程式碼實現：

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        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 是字串長度。right 和 left 指針分別只遍歷一次字串，每次移動都需要花費 O(1) 時間。
• 空間複雜度：O(min(n, m))，其中 m 是字符集大小，用於存儲集合中的字符。

解法二：優化滑動窗口 + 字典記錄

在前面的解法中，我們用集合檢查窗口內的字符是否有重複，但移除字符可能不夠高效。為了更進一步優化，可以用字典來記錄字符最後出現的位置。這樣，我們可以跳過中間多餘的字符，直接將 left 移動到重複字符的下一位置，這樣可以減少不必要的遍歷操作。

程式碼實現：

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        char_index = {}
        max_length = 0
        left = 0

        for right in range(len(s)):
            if s[right] in char_index and char_index[s[right]] >= left:
                left = char_index[s[right]] + 1  # 移動左指針
            char_index[s[right]] = right  # 更新字符位置
            max_length = max(max_length, right - left + 1)

        return max_length

• 時間複雜度：O(n)。在此解法中，我們每個字符只會被訪問一次，並且移動 left 指針到重複字符的下一個位置只需要 O(1) 的操作。
• 空間複雜度：O(min(n, m))，字典存儲每個字符的最後位置，節省了部分冗餘運算。

小結

這道題透過滑動窗口和雜湊結構的結合，可以有效地找到不重複的最長子字串。滑動窗口在字符檢查和位置跳躍方面能夠極大優化搜尋過程，學會這種技巧後，可以應用在許多字串處理的題目中。