ধরুন আমাদের দুটি স্ট্রিং S এবং T আছে, আমাদের S-এর ন্যূনতম সাবস্ট্রিং W খুঁজে বের করতে হবে, যাতে T হল W-এর পরবর্তী। যদি S-তে এমন কোনো উইন্ডো না থাকে যা T-এর সমস্ত অক্ষরকে কভার করে, তাহলে খালি স্ট্রিং ফেরত দিন। যদি এরকম একাধিক উইন্ডো থাকে, তাহলে আমাদেরকে বাম-সবচেয়ে শুরু হওয়া সূচী সহ একটি ফেরত দিতে হবে।
সুতরাং, যদি ইনপুটটি S ="abcdebdde", T ="bde" এর মতো হয়, তবে আউটপুটটি "bcde" হবে যেমনটি "bdde" এর আগে ঘটে। "deb" একটি ছোট উইন্ডো নয় কারণ উইন্ডোতে T-এর উপাদানগুলো অবশ্যই ক্রমানুসারে ঘটতে হবে।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
tidx :=0, tlen :=T
এর আকার -
n :=S
এর আকার -
i :=0, দৈর্ঘ্য :=inf, শুরু :=-1
-
যখন i
-
যদি S[i] T[tidx] এর মত হয়, তাহলে −
-
(1 দ্বারা tidx বাড়ান)
-
যদি tidx tlen এর মত হয়, তাহলে −
-
শেষ :=i + 1
-
(tidx 1 দ্বারা কমান)
-
যখন tidx>=0, do −
-
যদি S[i] T[tidx] এর মত হয়, তাহলে −
-
(tidx 1 দ্বারা কমান)
-
-
(i 1 দ্বারা কমান)
-
-
(i 1 দ্বারা বাড়ান)
-
(1 দ্বারা tidx বাড়ান)
-
যদি শেষ হয় - i <দৈর্ঘ্য, তারপর −
-
দৈর্ঘ্য :=শেষ - i
-
শুরু :=i
-
-
-
-
(i 1 দ্বারা বাড়ান)
-
-
যদি শুরু -1 এর সমান না হয়, তাহলে −
-
আরম্ভ করার জন্য i :=শুরু করুন, যখন i
-
ret :=ret + S[i>
-
-
-
রিটার্ন রিটার্ন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#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"
