সি++-এ মিনিমাম উইন্ডো সাবসিকোয়েন্স

ধরা যাক S এবং T নামে দুটি স্ট্রিং আছে, আমাদের S-এর মিনিমাম সাবস্ট্রিং W খুঁজে বের করতে হবে, যাতে T, W-এর একটি সাবসিকোয়েন্স হয়। যদি S-এ এমন কোনো উইন্ডো না থাকে যা T-এর সব ক্যারেক্টার কভার করে, তবে খালি স্ট্রিং রিটার্ন করুন। যদি একাধিক এমন উইন্ডো থাকে, তবে আমাদের লेफটমোস্ট স্টার্টিং ইন্ডেক্সের वालीটি রিটার্ন করতে হবে।

তাই, যদি ইনপুট S = "abcdebdde", T = "bde" হয়, তবে আউটপুট হবে "bcde" কারণ এটি "bdde"-এর আগে ঘটে। "deb" একটি ছোট উইন্ডো নয় কারণ উইন্ডোতে T-এর এলিমেন্টগুলো অর্ডারে থাকতে হবে।

এটি সমাধান করতে, আমরা নিচের ধাপগুলো অনুসরণ করব -

• tidx := 0, tlen := T-এর আকার

• n := S-এর আকার

• i := 0, length := inf, start := -1

• যখন i < n, করুন -

  • যদি S[i], T[tidx]-এর সমান হয়, তবে -

    • (tidx ১ করে বাড়ান)

    • যদি tidx, tlen-এর সমান হয়, তবে -

      • end := i + 1

      • (tidx ১ করে কমান)

      • যখন tidx >= 0, করুন -

        • যদি S[i], T[tidx]-এর সমান হয়, তবে -

          • (tidx ১ করে কমান)

        • (i ১ করে কমান)

      • (i ১ করে বাড়ান)

      • (tidx ১ করে বাড়ান)

      • যদি end - i < length, তবে -

        • length := end - i

        • start := i

  • (i ১ করে বাড়ান)

• যদি start, -1-এর সমান না হয়, তবে -

  • i := start থেকে শুরু করুন, যখন i < start + length, (i ১ করে বাড়ান), করুন -

    • ret := ret + S[i]

• ret রিটার্ন করুন

বेहतर বোঝার জন্য নিচের বাস্তবায়নটি দেখুন -

উদাহরণ

#include <bits/stdc++.h> using namespace std; class Solution {    public:    string minWindow(string S, string T) {       int tidx = 0;       int tlen = T.size();       int n = S.size();       int i = 0;       int length = INT_MAX;       int start = -1;       string ret;       while (i < n) {          if (S[i] == T[tidx]) {             tidx++;             if (tidx == tlen) {                int end = i + 1;                tidx--;                while (tidx >= 0) {                   if (S[i] == T[tidx]) {                      tidx--;                   }                   i--;                }                i++;                tidx++;                if (end - i < length) {                   length = end - i;                   start = i;                }             }          }          i++;       }       if (start != -1)       for (int i = start; i < start + length; i++)       ret += S[i];       return ret;    } }; main(){    Solution ob;    cout << (ob.minWindow("abcdebdde", "bde")); }

ইনপুট

"abcdebdde", "bde"

আউটপুট

"bcde"