題目描述
給定一個字串 s，請找出其中不含重複字母的最長子字串的長度。
例如：
- 輸入：
s = "abcabcbb"
輸出：3（最長的不重複子字串是"abc"，其長度為 3） - 輸入：
s = "bbbbb"
輸出：1（最長的不重複子字串是"b"，其長度為 1） - 輸入：
s = "pwwkew"
輸出：1（最長的不重複子字串是"wke"，其長度為 3）
解題思路
此題的目標是找出字串中不含重複字母的最長子字串的長度，重點在於找到每個子字串，並確保子字串內部沒有重複的字母。這裡我們可以運用滑動窗口來解題。滑動窗口是一種雙指針技術，適合用來處理連續區間的問題。我們會使用一個滑動窗口遍歷字串，用一個集合儲存目前窗口中的字符，並且保持窗口內的字符唯一性。
解法一：滑動窗口 + 集合
步驟：
- 用
left和right指針來控制窗口，初始時都指向字串開頭。 - 用一個集合
char_set存儲當前窗口內的字符。 - 當
right指向的字符不在char_set時，將其加入集合，並更新最大長度。 - 當
right指向的字符在char_set中時，從left開始移除字符直到窗口內字符唯一。 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))，字典存儲每個字符的最後位置，節省了部分冗餘運算。
小結
這道題透過滑動窗口和雜湊結構的結合，可以有效地找到不重複的最長子字串。滑動窗口在字符檢查和位置跳躍方面能夠極大優化搜尋過程，學會這種技巧後，可以應用在許多字串處理的題目中。
