0076._Minimum_Window_Substring.md

76. Minimum Window Substring

难度:Hard

刷题内容

原题连接

• https://leetcode.com/problems/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.

思路 - 时间复杂度: O(N)- 空间复杂度: O(N)******

刚开始想到用 map 去做，但是这道题的键值是字符，因此可以用数组去做，这样时间复杂度为O(n)。想用一个数组每个字符出现的次数。接着遍历 s。固定一个区间，使在这个区间内的子字符串包含字符串 t，同样也可以用一个数组储存这个区间。接着向右移动区间即可。找到最短的区间。

class Solution {
public:
    string minWindow(string s, string t) {
        int arr[128],alNum = t.length();
        memset(arr,0,sizeof(arr));
        for(int i = 0;i < t.length();++i)
            arr[t[i]]++;
        vector<int> v;
        for(int i = 0;i < s.length();++i)
            if(arr[s[i]])
                v.push_back(i);
        int s_map[128],beg = -1,en,ans = INT_MAX,count1 = 0,l,r;
        memset(s_map,0,sizeof(s_map));
        for(int i = 0;i < v.size();++i)
        {
            if(count1 != alNum)
            {
                if(beg == -1)
                    beg = i;
                s_map[s[v[i]]]++;
                if(s_map[s[v[i]]] <= arr[s[v[i]]])
                    count1++;
            }
            for(int j = beg;count1 == alNum;)
            {
                en = v[i];
                s_map[s[v[j]]]--;
                if(ans > en - v[beg])
                {
                    l = v[beg];
                    r = en;
                    ans = en - v[beg];
                }
                if(s_map[s[v[j]]] < arr[s[v[j]]])
                    count1--;
                beg = ++j;
            }
       }
        if(ans == INT_MAX)
            return "";
        return s.substr(l,r - l + 1);
    }
};