题目

力扣题目链接

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

注意：

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

示例 1：

  1. 输入：s = "ADOBECODEBANC", t = "ABC"
  2. 输出："BANC"

示例 2：

  1. 输入：s = "a", t = "a"
  2. 输出："a"

示例 3:

  1. 输入: s = "a", t = "aa"
  2. 输出: ""
  3. 解释: t 中两个字符 'a' 均应包含在 s 的子串中，
  4. 因此没有符合条件的子字符串，返回空字符串。

提示：

  • 1 <= s.length, t.length <= 105
  • s 和 t 由英文字母组成

进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？

思路

做这道题之前，先把 209. 长度最小的子数组 和 904. 水果成篮 这两道题做了。

在本题中实现滑动窗口，主要确定如下三点：

  • 窗口内是什么？
  • 如何移动窗口的起始位置？
  • 如何移动窗口的结束位置？

以上

  • 窗口就是满足涵盖 t 所有字符的最小连续子数组。
  • 窗口的起始位置如何移动：如果当前窗口已经涵盖了 t 所有字符，即满足题意时，窗口就要向前移动了（也就是该缩小了）。
  • 窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，窗口的起始位置设置为数组的起始位置就可以了。

本题与 76. 最小覆盖子串 是非常相似的，只不过在子串的规则上更复杂，因此代码量会稍稍多一些。

我们可以使用 Map 来统计字符串 t 中各个字符出现的次数，同时再用一个 Map 保存滑动窗口内各个字符出现的次数。

当滑动窗口的右边界遍历字符串 s 的每个字符时，不断更新 Map 中的数据。

当滑动窗口内含有字符串 t 的所有字符 时（对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量 ），就可以开始尝试收缩滑动窗口的左边界了。

需要注意的是，不一定存在符合条件的子串，因此输出时要注意一下。

答案

Java

  1. class Solution {
  2.     public String minWindow(String s, String t) {
  3.         // 保存字符串 t 各个字符出现的次数
  4.         HashMap<Character, Integer> tmap = new HashMap<>();
  5.         // 遍历字符串 t 的每个字符
  6.         for (int k = 0; k < t.length(); k++) {
  7.             char c = t.charAt(k);
  9.             // 若当前字符是第一次出现
  10.             if (tmap.containsKey(c) == false) {
  11.                 // 将该字符串出现的次数标记为 1
  12.                 tmap.put(c, 1);
  13.             } else {
  14.                 // 将该字符串出现的次数标记为原有次数 +1
  15.                 Integer countTmp = tmap.get(c);
  16.                 tmap.put(c, countTmp + 1);
  17.             }
  18.         }
  20.         // 滑动窗口的起始下标
  21.         int i = 0;
  22.         // 滑动窗口的长度
  23.         int length = 0;
  24.         // 滑动窗口内涵盖字符串 t 多少个字符
  25.         int valid = 0;
  27.         // 保存滑动窗口内各个字符出现的次数
  28.         HashMap<Character, Integer> map = new HashMap<>();
  30.         // 答案, 从 answerIndex 下标起, 长度为 answerLength
  31.         int answerIndex = -1;
  32.         int answerLength = Integer.MAX_VALUE;
  34.         // 让滑动窗口的右边界遍历字符串 s 的每个字符
  35.         for (int j = 0; j < s.length(); j++) {
  36.             char c = s.charAt(j);
  38.             // 更新滑动窗口 map
  39.             // 若滑动窗口内已经含有当前字符
  40.             if (map.containsKey(c) == true) {
  41.                 // 更新该字符在滑动窗口内出现的次数 +1
  42.                 map.put(c, map.get(c) + 1);
  43.             } else {
  44.                 // 更新该字符串在滑动窗口内出现的次数为 1
  45.                 map.put(c, 1);
  46.             }
  48.             // 若该字符在滑动窗口内出现的次数 <= 若该字符在字符串 t 中出现的次数
  49.             if (map.get(c) <= tmap.getOrDefault(c, 0)) {
  50.                 // 滑动窗口内涵盖字符串 t 字符数 +1
  51.                 valid++;
  52.             }
  54.             // 判断当前滑动窗口内是否含有字符串 t 的所有字符
  55.             // 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量
  57.             // 若滑动窗口内涵盖字符串 t 字符数 = 字符串 t 的长度
  58.             while (valid == t.length()) {
  59.                 // 此时滑动窗口内的字符串是符合题意的有效子串, 但题目要求的是最小子串（有效子串：滑动窗口的字符涵盖 t 所有字符）
  60.                 // 记录子串长度和起始位置, 求长度最短的有效子串, 即为答案
  62.                 // 求当前滑动窗口的长度
  63.                 length = j - i + 1;
  64.                 // 若当前滑动窗口的长度更小
  65.                 if (length < answerLength) {
  66.                     // 更新答案
  68.                     // 起始位置为滑动窗口的左边界
  69.                     answerIndex = i;
  70.                     // 长度为滑动窗口的长度
  71.                     answerLength = length;
  72.                 }
  74.                 // 开始右移滑动窗口的左边界
  76.                 // 取滑动窗口左边界指向的字符, 并将左边界右移一位
  77.                 c = s.charAt(i++);
  78.                 // 若该字符在字符串 t 中出现过
  79.                 if (tmap.containsKey(c)) {
  80.                     // 若 该字符在滑动窗口中出现的次数 = 该字符在字符串 t 中出现的次数
  81.                     if (map.get(c).equals(tmap.get(c))) {
  82.                         // 说明左边界右移后, 滑动窗口内涵盖字符串 t 字符数 -1, 不满足题目要求
  83.                         valid--;
  84.                     }
  85.                 }
  87.                 // 更新该字符在滑动窗口内出现的次数, 因为上一步右移了滑动窗口的左边界, 所以 -1
  88.                 map.put(c, map.get(c) - 1);
  90.                 // 此时滑动窗口的左边界已被右移一位, 若 vaild 仍等于字符串 t 的长度, 将循环这个过程, 直到 valid < 字符串 t 的长度时, 才会跳出 while, 继续右移滑动窗口的右边界
  91.             }
  92.         }
  94.         // 若 answerIndex == -1, 说明在上述过程中, 没有找到任何一个符合题意的有效子串, 自然就不存在答案（最小子串）
  95.         if (answerIndex == -1) {
  96.             // 按照题目要求, 返回空字符串
  97.             return "";
  98.         }
  100.         // 返回答案
  101.         return s.substring(answerIndex, answerIndex + answerLength);
  102.     }
  103. }

REF

https://leetcode-cn.com/problems/minimum-window-substring/