ধরুন আমাদের দুটি স্ট্রিং s1 এবং s2 আছে, যদি s2-এ s1-এর পারমুটেশন থাকে তাহলে সত্য ফেরত দেওয়ার জন্য আমাদের একটি ফাংশন লিখতে হবে। তাই আমরা বলতে পারি যে প্রথম স্ট্রিং এর একটি পারমুটেশন হল দ্বিতীয় স্ট্রিং এর সাবস্ট্রিং। সুতরাং যদি স্ট্রিং s1 =“abc”, এবং দ্বিতীয় স্ট্রিং s2 হয় “findcab”, তাহলে ফলাফল সত্য হবে, কারণ “abc”-এর স্থানান্তর সত্য। সেটা হল "ক্যাব"৷
৷এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- 26 আকারের cnt1 এবং cnt2 দুটি ভেক্টর তৈরি করুন
- আমি 0 থেকে s1
- পরিসরে
- cnt1[s1[i] – 'a'] এর মান 1 দ্বারা বাড়ান
- j :=0 এবং প্রয়োজনীয় :=s1 এর আকার
- আমি 0 থেকে s2 এর আকারের মধ্যে
- x :=s2[i]
- cnt2[x – ‘a’] 1 দ্বারা বাড়ান
- যদি cnt1[x – ‘a’] এবং cnt2[x – ‘a’] <=cnt[x – ‘a’], তাহলে
- 1 দ্বারা কমাতে হবে
- যখন j <=i এবং cnt2[s2[j] – ‘a’] – 1>=cnt1[s2[j] – ‘a’], do
- cnt2[s2[j] – 'a'] 1 কমিয়ে দিন
- j 1 দ্বারা বাড়ান
- যদি i – j + 1 =s1 এর সাইজ এবং প্রয়োজনীয় =0, তাহলে true রিটার্ন করুন
- মিথ্যে ফেরত দিন।
উদাহরণ(C++)
আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool checkInclusion(string s1, string s2) {
vector <int> cnt1(26), cnt2(26);
for(int i = 0; i < s1.size(); i++)cnt1[s1[i] - 'a']++;
int j = 0;
int required = s1.size();
for(int i = 0; i < s2.size(); i++){
char x = s2[i];
cnt2[x - 'a']++;
if(cnt1[x - 'a'] && cnt2[x - 'a'] <= cnt1[x - 'a']) required--;
while(j <= i && cnt2[s2[j] - 'a'] - 1 >= cnt1[s2[j] - 'a']){
cnt2[s2[j] - 'a']--;
j++;
}
if(i - j + 1 == s1.size() && required == 0){
return true;
}
}
return false;
}
};
main(){
Solution ob;
cout << (ob.checkInclusion("abc", "findcab"));
} ইনপুট
"abc" "findcab"
আউটপুট
1
