C++ এ ন্যূনতম উইন্ডো সাবস্ট্রিং

ধরুন আমাদের একটি স্ট্রিং S এবং T আছে। আমাদের S-তে ন্যূনতম উইন্ডোটি খুঁজে বের করতে হবে যাতে T-এর সমস্ত অক্ষর থাকবে। সুতরাং ইনপুট যদি হয় “ABHDAXCVBAGTXATYCB” এবং T =“ABC”, তাহলে ফলাফল হবে:“ CVBA”।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি মানচিত্র তৈরি করুন m

• x এর ফ্রিকোয়েন্সি m

  এ সংরক্ষণ করুন

• দৈর্ঘ্য :=s এর আকার, বাম :=0, ডান :=0, ansLeft :=0 এবং ansRight :=0

• counter :=x এর আকার, পতাকা :=মিথ্যা, উত্তর :=খালি স্ট্রিং

• যখন উচ্চতা

  • c :=s[ডান]

  • যদি c থাকে m, তাহলে

    • যদি m[c]> 0 হয়, তাহলে কাউন্টার 1

      কমিয়ে দিন

    • 1

      দ্বারা m[c] হ্রাস করুন

  • যখন কাউন্টার =0 এবং বাম <=ডান

    • যদি ডান - বাম + 1 <=দৈর্ঘ্য

      • দৈর্ঘ্য :=ডান - বাম + 1

      • পতাকা :=সত্য

      • ansLeft :=left, ansRight :=right

    • যদি বাম =ডান, তাহলে লুপ ভাঙুন

    • c :=s[বাম]

    • যদি m এ c থাকে, তাহলে m[c] 1

      দ্বারা বাড়ান

    • যদি m[c]> 0 হয়, তাহলে কাউন্টার 1 দ্বারা বাড়ান

    • 1 দ্বারা বাম বাড়ান

  • ডান 1 দ্বারা বাড়ান

• যদি পতাকা মিথ্যা হয়, তাহলে উত্তর দিন

• অন্যথায় i রেঞ্জের জন্য উত্তর বাম থেকে উত্তর, s[i] দ্বারা উত্তর বাড়ান

• উত্তর ফেরত দিন

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

#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