摘要

最小覆盖子串问题是一个经典的滑动窗口算法问题，用于在源字符串中找到包含目标字符串所有字符的最短子串。本文详细解析基于滑动窗口和字符计数的算法实现，包括输入解析、窗口扩展收缩、字符计数匹配等核心功能的代码细节。

1. 算法背景

1.1 问题描述

给定两个字符串 source 和 target，在 source 中找到包含 target 所有字符的最短连续子串。注意：

• 需要包含 target 中的所有字符（包括重复字符）
• 子串必须是连续的
• 返回最短的子串

示例：

• source = "ADOBECODEBANC", target = "ABC"
• 答案："BANC"（最短的包含 A、B、C 的子串）

1.2 应用场景

• 日志检索：在日志中找到包含特定关键字的最短片段
• 文本搜索：搜索引擎中的关键词高亮
• 数据流分析：找到包含特定模式的最小时间窗口
• 字符串匹配：模糊匹配和近似匹配

2. 核心算法原理

使用滑动窗口（Sliding Window）算法：

1. 扩展窗口：右指针向右移动，扩大窗口
2. 收缩窗口：当窗口满足条件时，左指针向右移动，缩小窗口
3. 字符计数：使用哈希表记录窗口中每个字符的出现次数
4. 匹配判断：检查窗口是否包含目标字符串的所有字符

3. 代码实现详细解析

3.1 输入解析模块

var source: String? = null
var target: String? = null

val lines = payload.lines().map { it.trim() }.filter { it.isNotEmpty() }
lines.forEach { line ->
    when {
        line.startsWith("source=", ignoreCase = true) -> source = line.substringAfter("=").trim()
        line.startsWith("target=", ignoreCase = true) -> target = line.substringAfter("=").trim()
    }
}
if (source == null && lines.isNotEmpty()) {
    source = lines.first()
}
if (target == null && lines.size >= 2) {
    target = lines[1]
}

代码解析：

这段代码实现了灵活的输入解析机制，支持两种输入格式。首先使用函数式编程风格处理输入：payload.lines() 将输入按行分割，map { it.trim() } 去除每行的首尾空白，filter { it.isNotEmpty() } 过滤空行，得到一个干净的字符串列表。

然后遍历每一行，使用 when 表达式匹配不同的输入格式。如果行以 source= 开头（忽略大小写），使用 substringAfter("=") 提取等号后面的值，并用 trim() 去除空白。同样的方式处理 target= 格式。

如果键值对格式解析失败，代码采用后备方案：第一行作为 source，第二行作为 target。这种双重解析策略提高了用户体验，用户无需记忆特定格式。isNotEmpty() 和 size >= 2 检查确保有足够的行数，避免数组越界。

3.2 边界条件检查

if (t.length > s.length) {
    return "❌ target 长度大于 source，无法覆盖"
}

代码解析：

这是重要的边界条件检查。如果目标字符串的长度大于源字符串，显然无法在源字符串中找到包含目标字符串所有字符的子串。提前返回可以避免后续无意义的计算，提高算法效率。

这种防御性编程思想在算法实现中非常重要，能够处理各种边界情况，避免程序崩溃或产生错误结果。

3.3 字符频次统计初始化

val need = mutableMapOf<Char, Int>()
for (c in t) need[c] = (need[c] ?: 0) + 1
val window = mutableMapOf<Char, Int>()

var haveTypes = 0
val needTypes = need.size

代码解析：

这部分代码初始化了算法所需的数据结构，是算法的核心基础设施。

need 是一个可变映射表，用于存储目标字符串中每个字符需要的数量。遍历目标字符串 t，对每个字符 c，使用 need[c] = (need[c] ?: 0) + 1 累加计数。need[c] ?: 0 使用 Elvis 操作符，如果字符 c 不在映射表中则返回 0，然后加 1。这样即使字符重复出现，也能正确统计每个字符需要的数量。例如，如果 target = "AABC"，则 need['A'] = 2，need['B'] = 1，need['C'] = 1。

window 是另一个可变映射表，用于记录当前滑动窗口中每个字符的实际数量。初始时窗口为空，所有字符计数为 0。

haveTypes 变量记录当前窗口中已经满足需求（即数量达到 need 中要求）的字符类型数量。needTypes 是目标字符串中不同字符类型的总数，即 need.size。当 haveTypes == needTypes 时，说明窗口已经包含了目标字符串的所有字符（包括重复字符），窗口满足条件。

这种设计避免了每次都要遍历整个 need 和 window 来检查是否满足条件，只需要维护一个计数器，大大提高了效率。

3.4 窗口扩展和收缩的辅助函数

fun expandCount(c: Char) {
    window[c] = (window[c] ?: 0) + 1
    if (need.containsKey(c) && window[c] == need[c]) {
        haveTypes += 1
    }
}

fun shrinkCount(c: Char) {
    if (need.containsKey(c) && window[c] == need[c]) {
        haveTypes -= 1
    }
    window[c] = (window[c] ?: 0) - 1
}

代码解析：

这两个辅助函数封装了窗口扩展和收缩时的字符计数逻辑，使主循环代码更清晰。

expandCount 函数在窗口扩展时调用，当右指针向右移动，新字符 c 进入窗口时使用。首先将字符 c 的计数加 1：window[c] = (window[c] ?: 0) + 1。然后检查这个字符是否满足需求：need.containsKey(c) 确保字符 c 是目标字符串中的字符，window[c] == need[c] 检查当前窗口中的数量是否刚好达到需求。如果满足，haveTypes 加 1，表示又有一个字符类型满足了需求。

注意这里使用 == 而不是 >=，是因为我们只关心刚好达到需求的情况。如果 window[c] > need[c]，说明这个字符已经满足需求了，不需要重复计数。这种精确匹配的设计确保了 haveTypes 的准确性。

shrinkCount 函数在窗口收缩时调用，当左指针向右移动，字符 c 离开窗口时使用。逻辑与 expandCount 相反：首先检查如果这个字符当前刚好满足需求（window[c] == need[c]），那么在减少计数之前，需要将 haveTypes 减 1，因为减少后就不满足需求了。然后才将字符计数减 1。

注意顺序很重要：必须先检查是否满足需求并更新 haveTypes，然后再更新 window[c]。如果顺序颠倒，window[c] == need[c] 的判断就会出错。

这两个函数的设计体现了封装和代码复用的思想，将复杂的计数逻辑提取出来，使主循环更易读易维护。

3.5 核心滑动窗口循环

for (right in s.indices) {
    expandCount(s[right])
    while (haveTypes == needTypes && left <= right) {
        val windowLen = right - left + 1
        if (windowLen < bestLen) {
            bestLen = windowLen
            bestL = left
            bestR = right
        }
        shrinkCount(s[left])
        left += 1
    }
}

代码解析：

这是算法的核心部分，实现了滑动窗口的主要逻辑。外层循环使用 for (right in s.indices) 遍历源字符串，right 是右指针，从 0 开始向右移动。s.indices 返回字符串的有效索引范围，比手动写 0 until s.length 更简洁。

每次循环，首先调用 expandCount(s[right]) 将右指针指向的字符加入窗口。这个字符可能是目标字符串中的字符，也可能不是。如果是目标字符，可能会使 haveTypes 增加。

然后进入内层 while 循环，条件是 haveTypes == needTypes && left <= right。第一个条件表示窗口已经包含了目标字符串的所有字符，第二个条件 left <= right 确保左指针不超过右指针，避免无效窗口。

当窗口满足条件时，计算当前窗口的长度 windowLen = right - left + 1（注意加 1，因为左右指针都包含在内）。如果这个长度小于之前记录的最优长度 bestLen，更新最优解：记录新的长度、左指针位置和右指针位置。

然后尝试收缩窗口：调用 shrinkCount(s[left]) 将左指针指向的字符移出窗口，left += 1 将左指针向右移动一位。收缩后继续检查窗口是否还满足条件，如果满足则继续收缩，寻找更短的子串；如果不满足则退出内层循环，继续扩展窗口。

这个算法的精妙之处在于：当窗口满足条件时，我们记录当前最优解，然后尝试收缩窗口寻找更短的解。如果收缩后窗口不再满足条件，说明刚才的窗口已经是最短的满足条件的窗口了，继续扩展寻找下一个满足条件的窗口。

3.6 结果处理和覆盖统计

if (bestLen == Int.MAX_VALUE) {
    builder.appendLine("❌ 未找到覆盖 target 的子串")
} else {
    val substring = s.substring(bestL, bestR + 1)
    builder.appendLine("✅ 最短覆盖子串长度: $bestLen")
    builder.appendLine("窗口区间: [$bestL, $bestR]")
    builder.appendLine("子串内容: \"$substring\"")
    
    val coverage = need.map { (c, n) ->
        val count = substring.count { it == c }
        "$c: 需要 $n / 实际 $count"
    }
    builder.appendLine("📊 覆盖统计: ${coverage.joinToString("; ")}")
}

代码解析：

这部分代码处理算法的输出结果，包括结果验证和详细的统计信息。

首先检查 bestLen 是否仍为 Int.MAX_VALUE（初始值）。如果是，说明整个算法过程中没有找到满足条件的窗口，返回未找到的结果。否则，使用 s.substring(bestL, bestR + 1) 提取最优子串。注意 substring 的第二个参数是 bestR + 1，因为 substring 的结束索引是不包含的。

然后输出最短子串的长度、窗口区间和子串内容，让用户清楚地看到结果。

覆盖统计部分使用 need.map 遍历目标字符串中的每个字符，对每个字符 c 和其需求数量 n，统计子串中该字符的实际出现次数 count。使用字符串模板生成格式化的统计信息，例如 "A: 需要 1 / 实际 1"。最后使用 joinToString("; ") 将所有统计信息用分号连接，形成清晰的输出。

这个统计功能对于验证结果的正确性非常有用，用户可以直观地看到每个字符是否满足需求。

4. 算法复杂度分析

4.1 时间复杂度

• 字符串遍历：O(n)，n 为源字符串长度
• 窗口扩展：每个字符最多被访问一次，O(n)
• 窗口收缩：每个字符最多被访问一次，O(n)
• 总体时间复杂度：O(n)

虽然看起来有嵌套循环，但实际上每个字符最多被左右指针各访问一次，所以总时间复杂度是线性的。

4.2 空间复杂度

• 字符频次映射：O(k)，k 为不同字符种类数（最多 26 个字母）
• 窗口映射：O(k)
• 其他变量：O(1)
• 总体空间复杂度：O(k)，通常 k 远小于 n

5. 算法优化建议

5.1 空间优化

如果字符集较小（如只有字母），可以使用数组代替哈希表：

val need = IntArray(128)  // ASCII 字符

5.2 性能优化

• 提前终止：如果找到长度等于目标字符串长度的子串，可以提前返回
• 字符集过滤：只处理目标字符串中出现的字符，忽略其他字符

6. 应用场景扩展

1. 多模式匹配：扩展为同时匹配多个目标字符串
2. 加权匹配：不同字符有不同的重要性权重
3. 模糊匹配：允许一定数量的字符不匹配
4. 最长覆盖子串：找到最长的满足条件的子串

7. 总结

最小覆盖子串算法是滑动窗口技术的经典应用，本文详细解析了算法的每个实现细节。核心要点：

1. 滑动窗口：使用双指针技术，时间复杂度 O(n)
2. 字符计数：使用哈希表记录字符频次，支持重复字符
3. 匹配判断：通过计数器 haveTypes 高效判断窗口是否满足条件
4. 窗口收缩：满足条件时尝试收缩窗口，寻找最短解

通过深入理解代码实现，可以更好地应用滑动窗口算法解决实际问题，如文本搜索、日志分析、数据流处理等场景。

欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.csdn.net