Chuỗi cửa sổ tối thiểu trong C ++

Giả sử chúng ta có một chuỗi S và T. Chúng ta phải tìm cửa sổ tối thiểu trong S chứa tất cả các ký tự trong T. Vì vậy, nếu đầu vào là “ABHDAXCVBAGTXATYCB” và T =“ABC”, thì kết quả sẽ là:“ CVBA ”.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Tạo một bản đồ m

• lưu tần số của x thành m

• length:=size of s, left:=0, right:=0, ansLeft:=0 và ansRight:=0

• counter:=size of x, flag:=false, ans:=blank string

• trong khi chiều cao

  • c:=s [right]

  • nếu c có trong m thì

    • nếu m [c]> 0, thì giảm bộ đếm đi 1

    • giảm m [c] đi 1

  • trong khi counter =0 và left <=right

    • nếu phải - trái + 1 <=length

      • length:=right - left + 1

      • cờ:=true

      • ansLeft:=left, ansRight:=right

    • nếu left =right, thì ngắt vòng lặp

    • c:=s [left]

    • nếu c có trong m thì tăng m [c] thêm 1

    • nếu m [c]> 0, thì tăng bộ đếm lên 1

    • tăng bên trái 1

  • tăng quyền lên 1

• nếu cờ sai, thì trả về ans

• ngược lại đối với tôi trong phạm vi ansLeft to ansRight, hãy tăng ans lên s [i]

• trả lại ans

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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"));
}

Đầu vào

"ABHDAXCVBAGTXATYCB"
"ABC"

Đầu ra

CVBA