【LeetCode】76. Minimum Window Substring

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).
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.
【分析】
題意:所与の文字列Sから所与の文字列Tの全ての文字を含む最小子列を探す.
最小子列を探す以上、遍歴文字列Sは避けられないが、Sの各文字を遍歴する際には、その文字がTに含まれる文字であるか否かを判断し、文字の重複の可能性を考慮して、Sを遍歴する際に含まれるTに存在する文字の出現回数を判断する必要がある.これに鑑みて、Tに含まれる文字とその数を記録するために「ハッシュテーブル」を採用した.このように判断を極めて簡略化することができ、具体的には:
1、与えられた文字列は大文字と小文字のみを含むため、そのASCII範囲は[65,90],[97122]であり、差を避けるためにハッシュテーブル長は128とすることができ、Tのi番目の文字に対応するハッシュテーブルの記憶位置には以下のように:T[i];実際、ハッシュテーブルの長さは57=122-65であってもよいが、このようにすれば、Tのi番目の文字がハッシュテーブルに対応する記憶位置は、空間、時間の重要性に応じてその1つを選択することができるT[i]-'A'と表記される.
2、文字列Tを一度遍歴すれば、ハッシュテーブルに含まれる文字とその数を記録することができる.
3、次に文字列Sを巡回し、スライドウィンドウを作成し、先頭ポインタをbegin=end=0に初期化し、end+1文字目まで巡回した場合、スライドシリアルポート[begin,end]がT中のすべての文字(回数を含む)を初めて含んだ場合、サブシリアル長さを記録する.
4、その後、最初のポインタbeginを徐々に圧縮し、このウィンドウにT中の文字が完全に含まれないまで、最小サブ列の長さを更新し、beginの移動を停止し、endの移動に変更する.ウィンドウが再びTのすべての文字を含む場合、endがSの末尾を指し、beginがTのすべての文字を完全に含むことができないまで圧縮するまで、上記の手順を繰り返す.
5、最後に、記録された最小ウィンドウの文字列を返します.
【解法及び注釈】

class Solution {
public:
    string minWindow(string s, string t) {
        
        vector<int> count(60,0);//  T             ，           
        vector<bool> flag(60,false);//  T      
        int sum=t.size();//t     
        int copyBegin=0;//      
        int begin=0;//        
        int end=0;
        int minsize=s.size()+1;//   s      t   ，       ，          <=s.size()
        
        for(int i=0;i<t.size();i++)//     t，       ，     
        {
            count[t[i]-'A']++;
            flag[t[i]-'A']=true;
        }
        
        for(int j=0;j<s.size();j++)//     s
        {
            if(flag[s[j]-'A'])//  s      t   ,  ，      
            {
                count[s[j]-'A']--;//        ，       s      t
                if(count[s[j]-'A']>=0)//s            t       ，    ==0，         
                sum--;
            }
            
            
            while(sum==0)//     t        
            {
                if(end-begin+1<minsize)//            
                {
                  minsize=end-begin+1;
                  copyBegin=begin;
                }
                
                if(flag[s[begin]-'A'])//      begin ,         t   ，    
                {
                  count[s[begin]-'A']++;
                  if(count[s[begin]-'A']>0)//        ，         ，    
                  sum++;                   //  ，          t   ，while()        ，end  
                }
                begin++;//    
            }
            end++;
        }
        if(minsize>s.size())return "";//    ，   
        else return s.substr(copyBegin,minsize);//      
        
    }
};