https://leetcode.com/problems/minimum-window-substring/description/

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).

For example,

S = "ADOBECODEBANC"

T = "ABC"

Minimum window is "BANC".

Note:

If there is no such window in S that covers all characters in T, return the empty string "".

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

---

• 字符串中等题。Sliding window algorithm + Hash。
• 设置window start/end,  扩展end去找到符合条件的window，找到之后再扩展start来缩小window找到min window substring。

1 // 2 //  main.cpp 3 //  LeetCode 4 // 5 //  Created by Hao on 2017/3/16. 6 //  Copyright © 2017年 Hao. All rights reserved. 7 // 8  9 #include 
        
         10 #include 
         
          11 #include 
          
           12 using namespace std;13 14 class Solution {15 public:16     string minWindow(string s, string t) {17         if (s.empty() || t.empty()) return "";18         19         string sResult;20         unordered_map
           
             hash;21         22         for (auto & ch : t)23             ++ hash[ch];24         25         // window start/end, sum{positive hash[i]}, min window size26         int left = 0, right = 0, count = t.size(), len = INT_MAX;27         28         while (right < s.size()) {29             if (hash[s.at(right)] > 0)30                 -- count;31             32             -- hash[s.at(right)];33             34             ++ right;35             36             // found the valid window37             while (0 == count) {38                 if (right - left < len) { // find the min window39                     len = right - left;40                     sResult = s.substr(left, len);41                 }42                 43                 // move window left to minimize window, and restore hash value/count when kick out left point44                 if (hash[s.at(left)] >= 0)45                     ++ count;46                 47                 ++ hash[s.at(left)];48                 49                 ++ left;50             }51         }52         53         if (len == INT_MAX)54             sResult = "";55         56         return sResult;57     }58 };59 60 int main(int argc, char* argv[])61 {62     Solution    testSolution;63     64     vector
            
               sInputs = {
      "ADOBECODEBANC", "", "A", "ABC"};65     vector
             
               tInputs = { "ABC", "A", "", "DEF"};66 string result;67 68 /*69 "BANC"70 ""71 ""72 ""73 */74 for (auto i = 0; i < sInputs.size(); ++ i) {75 result = testSolution.minWindow(sInputs[i], tInputs[i]);76 cout << "\"" << result << "\"" << endl;77 }78 79 return 0;80 }