leetcode76 -- Minimum Window Substring (HARD)

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.



class Solution {
public:
    string minWindow(string s, string t) {
        string res = "";
        unordered_map<char, int> letterCnt;
        int left = 0, cnt = 0, minLen = INT_MAX;  //其实minLen初始化为len(s)+1就可以了
        for (char c : t) ++letterCnt[c];   //建立t的字典.
        
        for (int i = 0; i < s.size(); ++i) {
            if (--letterCnt[s[i]] >= 0) ++cnt;   //如果这个出现过,就让对应的去掉1.
            while (cnt == t.size()) {   //这时候开启从左边缩的模式
                if (minLen > i - left + 1) {    //更新最小模式
                    minLen = i - left + 1;
                    res = s.substr(left, minLen);
                }
                if (++letterCnt[s[left]] > 0) --cnt;
                ++left;
            }
        }
        return res;
    }
};

这个采用的是双指针的办法,即先是向右边扩展,找到包括T的子串,然后再看看从左边能不能去掉一些,使得其尽可能地短,这样才能得到尽可能短的字符串.

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦