76. Minimum Window Substring，minimumsubstring

76. Minimum Window Substring，minimumsubstring

LeetCode
Explore
Problems
Mock 
Contest
Articles
Discuss
 Store 
 Premium
New Playground
lifeqiuzhi520

76. Minimum Window Substring
DescriptionHintsSubmissionsDiscussSolution
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.
Seen this question in a real interview before?  No
Thanks for your feedback.
Difficulty:Hard
Total Accepted:173.4K
Total Submissions:615.7K
Contributor:LeetCode
Subscribe to see which companies asked this question.

Related Topics 

Similar Questions 
Substring with Concatenation of All WordsMinimum Size Subarray SumSliding Window MaximumPermutation in StringSmallest RangeMinimum Window Subsequence
C++	

string minWindow(string s, string t) {
        
    }
1
class Solution {
2
public:
3
    string minWindow(string S, string T) {
4
    string result;
5
    if(S.empty() || T.empty()){
6
        return result;
7
    }
8
    unordered_map<char, int> map;
9
    unordered_map<char, int> window;
10
    for(int i = 0; i < T.length(); i++){
11
        map[T[i]]++;
12
    }
13
    int minLength = INT_MAX;
14
    int letterCounter = 0;
15
    for(int slow = 0, fast = 0; fast < S.length(); fast++){
16
        char c = S[fast];
17
        if(map.find(c) != map.end()){
18
            window[c]++;
19
            if(window[c] <= map[c]){
20
                letterCounter++;
21
            }
22
        }
23
        if(letterCounter >= T.length()){
24
            while(map.find(S[slow]) == map.end() || window[S[slow]] > map[S[slow]]){
25
                window[S[slow]]--;
26
                slow++;
27
            }
28
            if(fast - slow + 1 < minLength){
29
                minLength = fast - slow + 1;
30
                result = S.substr(slow, minLength);
31
            }
32
        }
33
    }
34
    return result;
35
}
36
};
  Custom Testcase( Contribute  )
Submission Result: Accepted 
Next challenges: Minimum Size Subarray SumSliding Window MaximumPermutation in StringSmallest RangeMinimum Window Subsequence
Share your acceptance!
Check out our solution!


Type here...(Markdown is enabled)
​
Copyright © 2018 LeetCode Contact Us  |  Jobs  |  Students  |  Frequently Asked Questions  |  Terms of Service  |  Privacy Policy       United States