摘要

在日常開發中，我們經常需要處理字符串，比如分析用戶輸入、文本挖掘、數據清洗等等。而這道題就特別實用：如何找到一個字符串中最多包含 K 個不同字符的最長子串？本篇文章將用 Swift 手把手帶你搞懂滑動窗口的使用技巧，從思路到代碼再到復雜度分析，一站式搞定。

描述

題目是這樣描述的：

給定一個字符串 s 和一個整數 k，請你找出字符串中 最多包含 k 個不同字符的最長子串的長度。

這個問題的關鍵在于“最多包含 K 個不同字符”，也就是說超過 K 個不同字符就不符合要求，我們要把這個限制“滑動”管理好。

題解答案

我們使用 滑動窗口 + 哈希表 的經典組合來解決這個問題。滑動窗口主要用來維護當前的子串區間，而哈希表負責統計窗口內字符的出現頻次。

核心思路：

• 用兩個指針維護一個窗口 [left, right]
• 用一個 Dictionary<Character, Int> 來記錄當前窗口內每個字符的出現次數
• 如果窗口里的不同字符數超過 K，就不斷左移窗口直到滿足條件
• 在每次滿足條件的窗口中更新最大長度

題解代碼分析

func lengthOfLongestSubstringKDistinct(_ s: String, _ k: Int) -> Int {if k == 0 || s.isEmpty { return 0 }let chars = Array(s)var left = 0var maxLength = 0var charCount = [Character: Int]()for right in 0..<chars.count {let rightChar = chars[right]charCount[rightChar, default: 0] += 1// 當不同字符數量超過 k，移動左指針收縮窗口while charCount.keys.count > k {let leftChar = chars[left]charCount[leftChar]! -= 1if charCount[leftChar]! == 0 {charCount.removeValue(forKey: leftChar)}left += 1}// 記錄當前符合條件的最大長度maxLength = max(maxLength, right - left + 1)}return maxLength
}

詳細解析：

• charCount[rightChar, default: 0] += 1：把新字符加入窗口并計數
• charCount.keys.count > k：檢查窗口是否超出 K 種字符
• charCount.removeValue(forKey: leftChar)：清理掉數量為 0 的字符，保持哈希表干凈
• right - left + 1 是當前窗口長度，每次都嘗試更新最大值

示例測試及結果

print(lengthOfLongestSubstringKDistinct("eceba", 2)) // 輸出 3，子串為 "ece"
print(lengthOfLongestSubstringKDistinct("aa", 1))    // 輸出 2，子串為 "aa"
print(lengthOfLongestSubstringKDistinct("abcadcacacaca", 3)) // 輸出 11，子串為 "cadcacacaca"

結果解釋：

• 示例 1：子串 "ece" 有兩個不同字符，長度為 3
• 示例 2：整個字符串只有一種字符，直接返回長度 2
• 示例 3：可以從第 2 個字符開始算起，取到最長滿足條件的子串 "cadcacacaca"

時間復雜度

• 時間復雜度：O(n)
  整個字符串遍歷一遍，每個字符最多進出窗口一次。
• 空間復雜度：O(k)
  哈希表最多存儲 K 個不同字符的頻率。

總結

這道題是滑動窗口思想的經典應用，通過“收縮窗口”控制不同字符的種類，再通過變量記錄最長長度。在實際項目里，如果你在做關鍵詞搜索優化、用戶行為分析、或者簡單的文本壓縮策略，這類“限定種類數量”的需求其實挺常見的。

Swift 寫法也很清晰，用 Dictionary 來統計頻次，邏輯直觀，性能也不錯。