剑指 Offer II 017. 含有所有字符的最短字符串

题目链接

剑指 Offer II 017. 含有所有字符的最短字符串 hard

题目描述

给定两个字符串 s和 t。返回 s中包含 t的所有字符的最短子字符串。如果 s中不存在符合条件的子字符串，则返回空字符串 ""。

如果 s中存在多个符合条件的子字符串，返回任意一个。

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

示例 1：

输入：s = “ADOBECODEBANC”, t = “ABC”
输出：“BANC”
解释：最短子字符串 “BANC” 包含了字符串 t 的所有字符 ‘A’、‘B’、‘C’

示例 2：

输入：s = “a”, t = “a”
输出：“a”

示例 3：

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

提示：

• $1<=s.length,t.length<=10^5$
• s和 t由英文字母组成

分析：

本题用 滑动窗口 求解。

用哈希表 ht记录 t中字符的出现次数。

再用另一个哈希表 hs记录 s滑动窗口区间的字符出现次数。

用两个指针 i和 j分别维护滑动窗口的左边界 和 右边界。

如果 hs[s[j]] <= ht[s[j]]，说明此时的 s[j]依旧是有效字符，区间有效字符数 cnt += 1。

如果 hs[s[i]] > ht[s[i]]，说明此时的区间内部字符已经超过了 t，所以收缩左区间，hs[s[i]]--，i++。

如果 cnt == t.size()，说明此时的区间 [l,r]包含了 t的所有字符，所以此时的 s.substr(i,j-i+1)可作为答案之一。

时间复杂度： $O(n)$

代码：

class Solution {
public:string minWindow(string s, string t) {int m = s.size() , n = t.size();if(m < n) return "";unordered_map<char,int> ht,hs;for(auto &c:t) ht[c]++;int len = 1e9,idx = -1;int cnt = 0;for(int i = 0,j = 0;j < m;j++){hs[s[j]]++;if(hs[s[j]] <= ht[s[j]]) cnt++;while(hs[s[i]] > ht[s[i]]){hs[s[i]]--;i++;}if(cnt == n){if(j - i + 1 < len){idx = i;len = j - i + 1;}}}return idx == -1 ? "" : s.substr(idx,len);}
};