0076. 最小覆盖子串 [Hard] [Minimum Window Substring].md

76. Minimum Window Substring

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.

---

题目：S中包含T所有字符的最小窗口。

思路：双指针。同时用一个map来记录子串中包含T中字符的个数。

工程代码下载

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> mp;
        for(auto c : t){
            mp[c]++;
        }
        int cnt = t.size();
        int i = 0, j = 0;  // 双指针
        int n = s.size();
        int start = 0, dist = INT_MAX;  // 初始化最小窗口信息
        while(j < n){
            while(j < n && cnt > 0){
                char c = s[j];
                if(mp.count(c) != 0){
                    if(mp[c]-- > 0)
                        --cnt;
                }
                j += 1;
            }

            // i到j的字符串已经包含了t中的所有字符，更新头指针，缩小dist
            while(i < j && cnt <= 0){
                int curlen = j - i;
                if(curlen < dist){
                    dist = curlen;
                    start = i;
                }
                char c = s[i];
                if(mp.count(c) != 0){
                    if(++mp[c] > 0)
                        ++cnt;
                }
                i += 1;
            }
        }
        return dist == INT_MAX ? "" : s.substr(start, dist);
    }
};

旧代码

#include<iostream>
#include<string>
#include<vector>
#include<numeric>
#include<unordered_map>
#include<limits>
using namespace std;

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> mp;
        for(auto c : t){
            ++mp[c];
        }
        int cnt = t.size();
        int start = 0, end = 0, head = 0;
        int dist = INT_MAX;  // 当前满足条件的字符长度
        while(end < s.size()){
            auto iter = mp.find(s[end]);
            if(iter != mp.end()){
                if(iter->second > 0)
                    --cnt;  // 需要组合成字符串t的字符个数减1
                --iter->second;
            }
            ++end;

            // begin到end的字符串已经包含了t中的所有字符，更新头指针，缩小dist
            while(cnt == 0){
                if(end - start < dist){
                    dist = end - start;
                    head = start;
                }
                auto iter = mp.find(s[start]);
                if(iter != mp.end()){
                    ++iter->second;
                    if(iter->second > 0)
                        ++cnt;
                }
                ++start;
            }
        }
        return dist == INT_MAX ? "" : s.substr(head, dist);
    }
};

int main()
{
    Solution sln;
    cout << sln.minWindow("ADOBECODEBANC", "ABC")<<endl;
    std::cout << "Hello World!\n";
}

---

Here is a 10-line template that can solve most 'substring' problems

Here comes the template.

For most substring problem, we are given a string and need to find a substring of it which satisfy some restrictions. A general way is to use a hashmap assisted with two pointers. The template is given below.

int findSubstring(string s){
        vector<int> map(128,0);
        int counter; // check whether the substring is valid
        int begin=0, end=0; //two pointers, one point to tail and one  head
        int d; //the length of substring

        for() { /* initialize the hash map here */ }

        while(end<s.size()){

            if(map[s[end++]]-- ?){  /* modify counter here */ }

            while(/* counter condition */){

                 /* update d here if finding minimum*/

                //increase begin to make it invalid/valid again

                if(map[s[begin++]]++ ?){ /*modify counter here*/ }
            }

            /* update d here if finding maximum*/
        }
        return d;
  }

The code of solving Longest Substring with At Most Two Distinct Characters is below:

int lengthOfLongestSubstringTwoDistinct(string s) {
        vector<int> map(128, 0);
        int counter=0, begin=0, end=0, d=0;
        while(end<s.size()){
            if(map[s[end++]]++==0) counter++;
            while(counter>2) if(map[s[begin++]]--==1) counter--;
            d=max(d, end-begin);
        }
        return d;
    }

The code of solving Longest Substring Without Repeating Characters is below:

int lengthOfLongestSubstring(string s) {
        vector<int> map(128,0);
        int counter=0, begin=0, end=0, d=0;
        while(end<s.size()){
            if(map[s[end++]]++>0) counter++;
            while(counter>0) if(map[s[begin++]]-->1) counter--;
            d=max(d, end-begin); //while valid, update d
        }
        return d;
    }