从字符串中“薅出”最长子串：LeetCode 340 Swift 解法全解析

摘要

在日常开发中，我们经常需要处理字符串，比如分析用户输入、文本挖掘、数据清洗等等。而这道题就特别实用：如何找到一个字符串中最多包含 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 = 0
    var maxLength = 0
    var 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]! -= 1
            if 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 来统计频次，逻辑直观，性能也不错。