leetcode76 - Minimum Window Substring - hard

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example:

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

Note:

  • If there is no such window in S that covers all characters in T, return the empty string "".
  • If there is such window, you are guaranteed that there will always be only one unique minimum window in S.
先用hashmap存好char2freq Sliding window,l, r框定区域,r往前移拓展范围,l往前移收缩范围,始终保证window里的substring包含了所有目标字符,找这个最小window size。 这里有一个小trick,r移动的时候,不论扫到的是不是目标字符,都在hashmap里对应的地方-1,因为不需要的字符默认存的值是0,需要的才有计数,那只要看减完之后val是否还大于等于0,是的话当前字符就是一个目标字符,用一个var来记录match,当match值和target string的长度一致时,r就可以先停一停了。 保证match值符合要求的情况下,先比较当前window size是不是最小的,是的话记录起始位置和长度,然后开始尝试缩进l,和刚刚的操作相反,l每次移动都给hashmap里对应的字符+1,不需要的字符刚刚被减过以后都小于0,目标字符被减了也至少为0,所以检查现在加完以后val是否大于0,是的话当前字符是一个目标字符,我们移动l的同时就会失去它,match要相应减小。match值不达标之后l就要停一停,继续开始移动r,直到遍历完整个souce string。 Time O(t+s)t是建map,s是traversal Space O(t+s)   corner cases: target长度>souce长度 直接返回“” 最后遍历结束要检查最小长度有没有被更改过,没有改过就是没找到,返回“”   注意点:r要移动是保证l不移或者l移完了再进行的,别match++的时候就r++了,先看看match达标没。外面的while loop用for loop可能会更清晰 写的过程中发现l往回缩进就破坏window条件的时候不知道该怎么办了,不用担心l继续动,因为已经记录过满足要求的区域了,l动了才能引导r去扩展,发现别的可能。   实现:
class Solution {
public:
    string minWindow(string s, string t) {
        
        if (t.size() > s.size()) return "";
        
        unordered_map<char, int> cnt;
        for (char c : t) cnt[c]++;
        
        int start = -1, min_len = INT_MAX;
        int l = 0, r = 0;
        int match = 0;
        while (r < s.size()){
            cnt[s[r]]--;
            if (cnt[s[r]] >= 0) match++;
            while (match == t.size()){
                if (r-l+1 < min_len){
                    start = l;
                    min_len = r-l+1;
                }
                cnt[s[l]]++;
                if (cnt[s[l]] > 0) match--;
                l++;
            }
            r++;
        }
        
        return min_len == INT_MAX ? "" : s.substr(start, min_len);
    
    }
};

 

上一篇:撤销 git pull 操作


下一篇:Arcoder abc162E.Sum of gcd of Tuples (Hard)