【每日算法】LeetCode 76. 最小覆盖子串

对前端开发者而言，学习算法绝非为了“炫技”。它是你从“页面构建者”迈向“复杂系统设计者”的关键阶梯。它将你的编码能力从“实现功能”提升到“设计优雅、高效解决方案”的层面。从现在开始，每天投入一小段时间，结合前端场景去理解和练习，你将会感受到自身技术视野和问题解决能力的质的飞跃。------ 算法：资深前端开发者的进阶引擎

LeetCode 76. 最小覆盖子串

1. 题目描述

给定一个字符串s和一个字符串t，返回s中涵盖t所有字符的最小子串。如果s中不存在涵盖t所有字符的子串，则返回空字符串""。

注意：

• 对于t中重复字符，我们寻找的子字符串中该字符数量必须不少于t中该字符数量。
• 如果s中存在这样的子串，我们保证它是唯一的答案。

示例：

• 输入：s = "ADOBECODEBANC",t = "ABC"
• 输出："BANC"
• 解释：最小子串 “BANC” 包含 ‘A’、‘B’ 和 ‘C’。

2. 问题分析

这是一个典型的子串覆盖问题，需要从字符串s中找到最短的连续子串，使得该子串包含字符串t的所有字符（包括重复字符）。问题本质是优化搜索过程，避免枚举所有子串。

前端视角：在前端开发中，类似场景包括用户输入过滤（如搜索框自动完成）、文本高亮匹配或动态内容渲染，其中需要高效处理字符串以提供实时响应。

3. 解题思路

3.1 暴力法（Brute Force）

枚举s的所有子串，检查每个子串是否覆盖t，并记录最小长度。这种方法简单但效率低下，不适用于长字符串。

复杂度：

• 时间复杂度：O(n^3)，其中 n 是s的长度（枚举子串 O(n^2)，检查覆盖 O(n)）。
• 空间复杂度：O(m)，用于存储t的字符计数，m 是t中字符集大小。

3.2 滑动窗口法（Sliding Window，最优解）

使用两个指针left和right在s上定义窗口，通过移动指针动态调整窗口大小。用哈希表记录字符需求，确保窗口覆盖t的所有字符。

步骤：

1. 初始化哈希表need，记录t中每个字符所需数量。
2. 使用left = 0、right = 0滑动窗口，valid计数满足需求的字符种类数。
3. 扩展right指针，增加窗口，直到窗口覆盖t。
4. 收缩left指针，缩小窗口，同时更新最小子串。
5. 重复直到right到达s末尾。

复杂度：

• 时间复杂度：O(n)，其中 n 是s的长度，每个字符最多被访问两次。
• 空间复杂度：O(m)，用于哈希表存储，m 是字符集大小（如 ASCII 为 128）。

最优解：滑动窗口法是最优解，因为它在线性时间内解决问题。

4. 各思路代码实现

4.1 暴力法实现（JavaScript）

functionminWindowBruteForce(s,t){if(s.length<t.length)return"";constneed=newMap();for(letcharoft){need.set(char,(need.get(char)||0)+1);}letminLen=Infinity,minStr="";for(leti=0;i<s.length;i++){for(letj=i+t.length;j<=s.length;j++){constsubstr=s.substring(i,j);if(isCover(substr,newMap(need))){if(substr.length<minLen){minLen=substr.length;minStr=substr;}break;// 找到覆盖就跳出内层循环，因为继续扩展只会更长}}}returnminStr;}functionisCover(substr,need){for(letcharofsubstr){if(need.has(char)){need.set(char,need.get(char)-1);if(need.get(char)===0)need.delete(char);}}returnneed.size===0;}// 测试console.log(minWindowBruteForce("ADOBECODEBANC","ABC"));// 输出 "BANC"

4.2 滑动窗口法实现（JavaScript，最优解）

functionminWindow(s,t){if(s.length<t.length)return"";constneed=newMap();constwindow=newMap();for(letcharoft){need.set(char,(need.get(char)||0)+1);}letleft=0,right=0;letvalid=0;// 满足需求的字符种类数letstart=0,minLen=Infinity;while(right<s.length){constchar=s[right];right++;// 更新窗口数据if(need.has(char)){window.set(char,(window.get(char)||0)+1);if(window.get(char)===need.get(char)){valid++;}}// 当窗口覆盖 t 时，收缩左侧while(valid===need.size){// 更新最小子串if(right-left<minLen){minLen=right-left;start=left;}constleftChar=s[left];left++;if(need.has(leftChar)){if(window.get(leftChar)===need.get(leftChar)){valid--;}window.set(leftChar,window.get(leftChar)-1);}}}returnminLen===Infinity?"":s.substring(start,start+minLen);}// 测试console.log(minWindow("ADOBECODEBANC","ABC"));// 输出 "BANC"console.log(minWindow("a","aa"));// 输出 ""

5. 各实现思路的复杂度、优缺点对比表格

6. 总结

LeetCode 76. 最小覆盖子串问题展示了滑动窗口算法的强大之处，它将复杂问题优化到线性时间。对于前端开发者，掌握此类算法不仅提升面试竞争力，更能应用于实际场景：

• 实际应用场景：
  • 搜索框自动完成：快速匹配用户输入的子串，提供实时建议。
  • 文本编辑器高亮：在长文档中高效查找并高亮关键词。
  • 数据过滤：在前端处理大型列表或字符串数据时，动态过滤覆盖特定模式的内容。
  • 性能优化：减少不必要的DOM操作或计算，确保用户界面流畅响应。