ধরুন আমাদের কাছে একটি স্ট্রিং S এবং T আছে। আমাদের কাজ হল S-এ সেই ন্যূনতম উইন্ডো (উপস্ট্রিং) খুঁজে বের করা যাতে T-এর সকল অক্ষর থাকে। যেমন, S = "ABHDAXCVBAGTXATYCB" এবং T = "ABC" হলে ফলাফল হবে "CVBA"।
সমাধানের ধাপসমূহ:
একটি ম্যাপ m তৈরি করুন।
T-এর অক্ষরগুলোর ফ্রিকোয়েন্সি m-এ সংরক্ষণ করুন।
length := S-এর আকার, left := 0, right := 0, ansLeft := 0, ansRight := 0
counter := T-এর আকার, flag := false, ans := খালি স্ট্রিং
যখন right < S.size() হয়:
c := S[right]
যদি c m-এ থাকে: যদি m[c] > 0 হয় তবে counter--; m[c]--
যখন counter == 0 এবং left <= right:
যদি right - left + 1 <= length: length আপডেট করুন, flag = true, ansLeft = left, ansRight = right
যদি left == right হয় তবে ব্রেক করুন
c := S[left], যদি c m-এ থাকে তবে m[c]++, যদি m[c] > 0 হয় তবে counter++
left++
right++
যদি flag false হয় তবে ans রিটার্ন করুন, অন্যথায় ansLeft থেকে ansRight পর্যন্ত অক্ষরগুলো 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;
}
};
int main() {
Solution ob;
cout << (ob.minWindow("ABHDAXCVBAGTXATYCB", "ABC"));
return 0;
}
ইনপুট
"ABHDAXCVBAGTXATYCB" "ABC"
আউটপুট
CVBA
