《剑指 Offer》专项突破版 - 面试题 17 : 包含所有字符的最短子字符串（C++ 实现）

题目链接：LCR 017. 最小覆盖子串 - 力扣（LeetCode）

题目：

输入两个字符串 s 和 t，请找出字符串 s 中包含字符串 t 中所有字符的最短子字符串。如果不存在符合条件的子字符串，则返回空字符串 ""。如果存在多个符合条件的子字符串，则返回任意一个。

注意：

对于 t 中重复字符，我们寻找的子字符串中该字符数量必不少于 t 中该字符数量。

示例 1：

输入：s = "ADDBANCAD", t = "ABC"
输出："BANC" 
解释：最短子字符串 "BANC" 包含了字符串 t 的所有字符 'A'、'B'、'C'

示例 2：

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

分析：

这又是一道关于统计子字符串中出现的字符及每个字符出现的次数的面试题。

有了前面的经验，就可以用一个哈希表来统计一个字符串中每个字符出现的次数。首先扫描字符串 t，每扫描到一个字符，就把该字符在哈希表中对应的值加 1。然后扫描字符串 s，每扫描一个字符，就检查哈希表中是否包含该字符，如果哈希表中没有该字符，则说明该字符不是字符串 t 中的字符，可以忽略不计；如果哈希表中存在该字符，则把该字符在哈希表中的对应值减 1。如果字符串 s 中的某个子字符串包含字符串 t 的所有字符，那么对应的哈希表中所有的值都应该小于或等于 0。

仍然可以用两个指针定位字符串 s 的子字符串，其中第 1 个指针指向子字符串的第 1 个字符，第 2 个指针指向子字符串的最后一个字符。

如果某一时刻两指针之间的子字符串还没有包含字符串 t 的所有字符，则在子字符串中添加新的字符，于是向右移动第 2 个指针。如果仍然没有包含字符串 t 的所有字符，则继续向右移动第 2 个指针。

如果某一时刻两指针之间的子字符串已经包含字符串 t 的所有字符，由于目标是找出最短的符合条件的子字符串，因此向右移动第 1 个指针，然后判断删除子字符串最左边的字符之后是否仍然包含字符串 t 的所有字符。

代码实现：

class Solution {
public:
 ? ?string minWindow(string s, string t) {
 ? ? ? ?int m = s.size(), n = t.size();
 ? ? ? ?if (m < n)
 ? ? ? ? ? ?return "";
?
 ? ? ? ?unordered_map<char, int> charToCount;
 ? ? ? ?for (int i = 0; i < n; ++i)
 ? ? ?  {
 ? ? ? ? ? ?++charToCount[t[i]];
 ? ? ?  }
?
 ? ? ? ?int totalCount = n;
 ? ? ? ?int left = 0, right = 0, minLeft = 0, minRight = 0;
 ? ? ? ?int minLength = m + 1;
 ? ? ? ?while (right < m || (right == m && totalCount == 0))
 ? ? ?  {
 ? ? ? ? ? ?if (totalCount > 0)
 ? ? ? ? ?  {
 ? ? ? ? ? ? ? ?if (charToCount.count(s[right]))
 ? ? ? ? ? ? ?  {
 ? ? ? ? ? ? ? ? ? ?--charToCount[s[right]];
 ? ? ? ? ? ? ? ? ? ?if (charToCount[s[right]] >= 0)
 ? ? ? ? ? ? ? ? ? ? ? ?--totalCount;
 ? ? ? ? ? ? ?  }
 ? ? ? ? ? ? ? ?++right;
 ? ? ? ? ?  }
 ? ? ? ? ? ?else ?// total == 0
 ? ? ? ? ?  {
 ? ? ? ? ? ? ? ?if (right - left < minLength)
 ? ? ? ? ? ? ?  {
 ? ? ? ? ? ? ? ? ? ?minLength = right - left;
 ? ? ? ? ? ? ? ? ? ?minLeft = left;
 ? ? ? ? ? ? ? ? ? ?minRight = right - 1;
 ? ? ? ? ? ? ?  }
?
 ? ? ? ? ? ? ? ?if (charToCount.count(s[left]))
 ? ? ? ? ? ? ?  {
 ? ? ? ? ? ? ? ? ? ?++charToCount[s[left]];
 ? ? ? ? ? ? ? ? ? ?if (charToCount[s[left]] == 1)
 ? ? ? ? ? ? ? ? ? ? ? ?++totalCount;
 ? ? ? ? ? ? ?  }
 ? ? ? ? ? ? ? ?++left;
 ? ? ? ? ?  }
 ? ? ?  }
?
 ? ? ? ?return minLength == m + 1 ? "" : s.substr(minLeft, minLength);
 ?  }
};

注意：

1. 变量 totalCount 是出现在字符串 t 中但还没有出现在字符串 s 的子字符串中的字符个数。

2. 这里哈希表使用了 C++ 中的类型 unordered_map，而没有和之前几个题目一样用数组模拟，是因为用类型 unordered_map 可以非常方便地判断一个字符在字符串 t 中是否出现，如果一个字符在字符串 t 中出现，那么哈希表中一定包含该字符的键。