1420 · minimum coverage substring II

describe

Give you a string S、 A string T,S It's cyclical , Please in string S Find it inside ： contain T The youngest string of all letters .

• If S There is no such substring in , Returns an empty string "".
• If S There is such a substring in , We guarantee that it is the only answer .

Examples

 Example 1:
 Input : 
S = "abcdc"
T = “da”
 Output : "dca"
 explain ： You can take S Rotate into  "bcdca", So your smallest covering substring is “dca”

 Example 2:
 Input :
S = "ADOBECODEBANC"
T = "DAOC"
 Output : "CADO"
 explain ： You can take S Rotate into "BECODEBANCADO",  Therefore, the minimum covering substring is “CADO”

 string minWindowII(string &S, string &T) {
     // Write your code here
     S = S + S;
     int tSize = T.size();
     int sSize = S.size();
     vector<bool>visited(sSize+1, false);
     map<char, int> tMap;
     for (int i = 0; i < tSize; i++)
     {
         auto it = tMap.find(T[i]);
         if (it != tMap.end())
         {
             tMap[T[i]]++;
         }
         else
         {
             tMap[T[i]]=1;
         }
     }
     int start = 0;
     int end = 0;
     int minStart=0;
     int minRet=INT_MAX;
     int tmpTsize = tSize;
     map<char, int> tMapTmp=tMap;
     while (start < sSize)
     {
        

         while (tmpTsize > 0 && end < sSize)
         {
             auto it = tMapTmp.find(S[end]);
             if (it != tMapTmp.end())
             {
                 it->second--;
                 if (it->second >= 0)
                 {
                     tmpTsize--;
                 }    
             }
             end++;    
         }
        
         while (tmpTsize == 0 && start < sSize)
         {
             if (end - start < minRet)
             {
                 minRet = end - start;
                 minStart = start;
             }

             auto it = tMapTmp.find(S[start]);
             if (it != tMapTmp.end())
             {    
                 it->second++;
                 if (it->second > 0)
                 {
                     tmpTsize++;
                 }            
             }    
             start++;    
         }

         if (end == sSize)
         {
             if (start == 0)
             {
                 break;
             }
             start++;
             end = start;

             if (visited[end] == true)
             {
                 break;
             }
             visited[end] = true;
             tMapTmp = tMap;
             tmpTsize = tSize;
         }
     }
     string sRet = "";
    for (int i = minStart; minRet != INT_MAX && i < minRet + minStart; i++)
     {
         sRet += S[i];
     }

     return sRet;
 }

 void test()
 {
     //string S = "abcdc";
     //string     T = "da"; //"dca"

     //string  S = "ADOBECODEBANC";
     //string     T = "DAOC";
         Output : "CADO"

     //string  S = "JCYHY";
     //string     T = "D";
     //string ret = minWindowII(S, T);

    // string  S = "eaGxRUaIOJ";
    // string     T = "Oax";

     //string  S = "PYXLzrJYdmUHpbxmSjObMdTrIXeuKxtyneqFJkyYaCMBUiKdqZRMOHAUDGuqI";
     //string     T = "zHqXF";
     FJkyYaCMBUiKdqZRMOHAUDGuqIPYXLz
     zrJYdmUHpbxmSjObMdTrIXeuKxtyneqF
     //string ret = minWindowII(S, T); //xRUaIlcGHiO

     string  S = "DwCBNuWUcAtrcqorVwOsILwgUNLTThdBtyZmeoGehPXGUarYCVqLjxysuzUM";
     string     T = "YqTdOZjYMM";
     //YCVqLjxysuzUMDwCBNuWUcAtrcqorVwOsILwgUNLTThdBtyZmeoGehPXGUarYCVqLjxysuzUM
     string ret = minWindowII(S, T);
 }