C++-এ স্ট্রিং-এ সব অ্যানাগ্রাম খুঁজে বের করা

মনে করুন একটি স্ট্রিং `s` এবং একটি নন-ইম্পটি স্ট্রিং `p` আছে, আমাদের `s`-এ `p`-এর সব অ্যানাগ্রামের শুরুর ইন্ডেক্সগুলো বের করতে হবে। স্ট্রিংগুলো শুধু लोওয়ারকেস লেটার দিয়ে তৈরি এবং `s` ও `p`-এর দৈর্ঘ্য যথাক্রমে ২০ এবং ১০০-এর চেয়ে বড় হবে না। উদাহরণস্বরূপ, যদি `s: "cbaebabacd"` এবং `p: "abc"` হয়, তবে আউটপুট হবে `[0, 6]`, ইন্ডেক্স ০-এ "cba", এবং অন্যটি "bac", এগুলো "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]` থাকে এবং `m[s[right]]` নন-জিরো হয়, তবে `right` ১ কমান, এবং লুপ থেকে বের হোন
  - যদি `m`-এ `s[left]` না থাকে, তবে `left := right + 1` সেট করুন
`ans` রিটার্ন করুন

উদাহরণ (C++)

বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশনটি দেখুন -

#include <bits/stdc++.h> using namespace std; void print_vector(vector<auto> v){    cout << "[";    for(int i = 0; i<v.size(); i++){       cout << v[i] << ", ";    }    cout << "]"<<endl; } class Solution { public:    vector<int> findAnagrams(string s, string p) {       map <char, int> m;       int n = s.size();       int left = 0, right = 0;       int counter = p.size();       vector <int> 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<right){                if(m.find(s[left]) != m.end()) {                   counter++;                   m[s[left]]++;                }                left++;                if(m.find(s[right]) != m.end() && m[s[right]]){                   right--;                   break;                }             }             if(m.find(s[left])==m.end())left = right + 1;          }       }       return ans;    } }; main(){    Solution ob;    print_vector(ob.findAnagrams("cbaebabacd", "abc")) ; }

ইনপুট

"cbaebabacd" "abc"

আউটপুট

[0, 6, ]