ধরুন আমাদের দুটি স্ট্রিং S এবং T আছে, আমাদের T-এ S-এর সকল অ্যানাগ্রামের স্টার্ট ইন্ডেক্স খুঁজে বের করতে হবে। স্ট্রিংগুলো শুধু ছোট হাতের অক্ষর ধারণ করে এবং S এবং T-এর দৈর্ঘ্য যথাক্রমে ২০ এবং ১০০ এর চেয়ে বড় হবে না।
ইনপুট: S = "cab", T = "bcabxabc" → আউটপুট: [0, 1, 5] কারণ সাবস্ট্রিং "bca", "cab", "abc"।
সমাধান পদ্ধতি
- একটি ম্যাপ m, n := S-এর সাইজ, left := 0, right := 0, counter := P-এর সাইজ
- এনসার অ্যারে ans ডিফাইন করুন
- P-র ক্যারেক্টার ফ্রিকোয়েন্সি ম্যাপ m-এ স্টোর করুন
- right = 0 থেকে n-1 পর্যন্ত লুপ করুন
- যদি m-এ s[right] থাকে এবং m[s[right]] নন-জিরো হয়, তবে m[s[right]] ১ কমান, counter ১ কমান, যদি counter = 0 হয় তবে left কে ans-এ যোগ করুন
- অন্যথায়, left < right পর্যন্ত লুপ করুন
- যদি s[left] m-এ না থাকে, তবে counter বাড়ান, m[s[left]] বাড়ান
- left বাড়ান
- যদি m-এ s[right] থাকে এবং নন-জিরো হয়, তবে right ১ কমান করে লুপ থেকে বের হোন
- যদি m-এ s[left] না থাকে, তবে left := right + 1 সেট করুন
- ans ফেরত দিন
বাস্তবায়ন (C++)
#include
using namespace std;
void print_vector(vector v){
cout << "[";
for(int i = 0; i findAnagrams(string s, string p) {
map m;
int n = s.size();
int left = 0, right = 0;
int counter = p.size();
vector ans;
for(int i = 0; i < p.size(); i++) m[p[i]]++;
for(int right = 0; right < n; right++){
if(m.find(s[right]) != m.end() && m[s[right]]){
m[s[right]]--;
counter--;
if(counter == 0)ans.push_back(left);
} else {
while(left ইনপুট
"bcabxabc", "cab"
আউটপুট
[0, 1, 5, ]
