C ++中的最小窗口子字符串

假设我们有一个字符串S和T。我们必须在S中找到将包含T中所有字符的最小窗口。因此，如果输入类似于“ ABHDAXCVBAGTXATYCB”和T =“ ABC”，那么结果将是： CVBA”。

为了解决这个问题，我们将遵循以下步骤-

• 创建一张映射

• 将x的频率存储到m

• 长度：= s的大小，左：= 0，右：= 0，ansLeft：= 0和ansRight：= 0

• counter：= x的大小，flag：= false，ans：=空字符串

• 而高度<s的大小-

• 如果是右–左+ 1 <=长度

• 如果left = right，则打破循环

• c：= s [左]

• 如果c存在于m中，则将m [c]加1

• 如果m [c]> 0，则将计数器增加1

• 向左增加1

• 长度：=右–左+ 1

• 标志：= true

• ansLeft：=左，ansRight：=右

• 如果m [c]> 0，则将计数器减1

• 将m [c]减少1

• c：= s [正确]

• 如果c存在于m中，则

• 而counter = 0且左<=右

• 向右增加1

• 如果flag为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