এই সমস্যায় দুটি স্ট্রিং s1 এবং s2 দেওয়া থাকলে, s2-তে s1-এর কোনো পারমুটেশন সাবস্ট্রিং হিসেবে আছে কিনা চেক করতে হবে।
উদাহরণ: s1="abc", s2="findcab" -> আউটপুট true (১)। কারণ "cab" হলো "abc"-এর পারমুটেশন।
সমাধানের পদ্ধতি (Sliding Window + Frequency Count)
s1-এর ক্যারেক্টার ফ্রিকোয়েন্সিcnt1[26]-এ স্টোর করুন।s2-এর ওপর স্লাইডিং উইন্ডো (সাইজ =s1.size()) চালান।- উইন্ডোর ফ্রিকোয়েন্সি
cnt2[26]-এ মেইনটেইন করুন। - যদি
cnt1 == cnt2হয়, তবেtrueরিটার্ন করুন।
উদাহরণ (C++)
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool checkInclusion(string s1, string s2) {
if (s1.size() > s2.size()) return false;
vector<int> cnt1(26, 0), cnt2(26, 0);
for (char c : s1) cnt1[c - 'a']++;
int windowSize = s1.size();
for (int i = 0; i < s2.size(); i++) {
cnt2[s2[i] - 'a']++;
if (i >= windowSize) {
cnt2[s2[i - windowSize] - 'a']--;
}
if (cnt1 == cnt2) return true;
}
return false;
}
};
int main() {
Solution ob;
cout << (ob.checkInclusion("abc", "findcab") ? "true" : "false");
return 0;
}
ইনপুট
"abc" "findcab"
আউটপুট
true
নোট: মূল কোডে একটি জটিল টু-পয়েন্টার অ্যাপ্রোচ দেওয়া ছিল, কিন্তু ফিক্সড সাইজ স্লাইডিং উইন্ডো সহজ এবং স্পষ্ট।
