C++での最小ウィンドウサブストリング

文字列SとTがあるとします。Tのすべての文字を含む最小ウィンドウをSで見つける必要があります。したがって、入力が「ABHDAXCVBAGTXATYCB」のようで、T =「ABC」の場合、結果は次のようになります。 CVBA」。

これを解決するには、次の手順に従います-

• 1つのマップを作成するm

• xの頻度をmに格納する

• 長さ：=sのサイズ、左：=0、右：=0、ansLeft：=0、ansRight：=0

• カウンター：=xのサイズ、フラグ：=false、ans：=空の文字列

• 高さ

  • c：=s [right]

  • cがmに存在する場合、

    • m [c]> 0の場合、カウンターを1減らします

    • m[c]を1減らします

  • カウンター=0で左<=右

    • 右の場合–左+1<=長さ

      • 長さ：=右–左+ 1

      • フラグ：=true

      • ansLeft：=左、ansRight：=右

    • 左=右の場合、ループを解除します

    • c：=s[左]

    • cがmに存在する場合は、m[c]を1増やします

    • m [c]> 0の場合、カウンターを1増やします

    • 左に1増加

  • 右に1増加

• フラグがfalseの場合は、ansを返します

• それ以外の場合、ansLeftからansRightの範囲にあるiの場合、ansをs [i]

  増やします。

• ansを返す

例

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   string minWindow(string s, string x) {
      map <char, int> m;
      for(int i =0;i<x.size();i++)m[x[i]]++;
      int length = s.size();
      int left = 0, right = 0 , ansLeft = 0, ansRight = 0;
      int counter = x.size();
      bool flag = false;
      string ans = "";
      while(right<s.size()){
         char c = s[right];
         if(m.find(c)!=m.end()){
            if(m[c]>0)counter--;
            m[c]--;
         }
         while(counter == 0 && left<=right){
            if(right-left+1 <=length){
               length = right-left+1;
               flag = true;
               ansLeft = left;
               ansRight = right;
            }
            if(left == right)break;
            c = s[left];
            if(m.find(c)!=m.end()){
               m[c]++;
               if(m[c]>0)counter++;
            }
            left++;
         }
         right++;
      }
      if(!flag)return ans;
      else
      for(int i =ansLeft;i<=ansRight;i++)ans+=s[i];
      return ans;
   }
};
main(){
   Solution ob;
   cout << (ob.minWindow("ABHDAXCVBAGTXATYCB", "ABC"));
}

入力

"ABHDAXCVBAGTXATYCB"
"ABC"

出力

CVBA