ধরুন আমাদের একটি স্ট্রিং s আছে, আমাদেরকে নিম্নলিখিত নিয়মগুলিকে সন্তুষ্ট করে এমন যেকোনো সাবস্ট্রিং-এর সর্বাধিক সংখ্যক উপস্থিতি খুঁজে বের করতে হবে -
- সাবস্ট্রিং-এ স্বতন্ত্র অক্ষরের সংখ্যা maxLetters-এর থেকে কম বা সমান হতে হবে।
- সাবস্ট্রিং সাইজ অবশ্যই মিনসাইজ এবং ম্যাক্সসাইজ ইনক্লুসিভ হতে হবে।
সুতরাং যদি ইনপুট হয় − “aababcaab”, maxLetters =2, minSize =3 এবং maxSize =4, তাহলে আউটপুট হবে 2। সাবস্ট্রিং "aab" এর মূল স্ট্রিংটিতে 2টি উপস্থিতি রয়েছে। এটি শর্ত পূরণ করে, 2টি অনন্য অক্ষর এবং আকার 3 (মিনিমাইজ এবং সর্বাধিক সাইজের মধ্যে)।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- একটি মানচিত্র m সংজ্ঞায়িত করুন
- sz-এর জন্য রেঞ্জ minSize থেকে maxSize
- একটি মানচিত্র x তৈরি করুন, একটি টেম্প তৈরি করুন, প্রাথমিকভাবে খালি
- আমি 0 থেকে sz – 1
- পরিসরে
- x[s[i]] 1 দ্বারা বাড়ান
- temp :=temp + s[i]
- j এর জন্য 0, i রেঞ্জ sz থেকে s – 1, i এবং j 1 দ্বারা বাড়ান
- যদি x <=maxLetters এর আকার হয়, তাহলে m[temp] 1 দ্বারা বাড়ান
- x[temp[0]] 1 কমিয়ে দিন
- যদি x[temp[0]] 0 হয়, তাহলে x থেকে temp[0] মুছে দিন
- টেম্প থেকেই টেম্পের প্রথম এবং দ্বিতীয় উপাদান মুছুন
- x[s[i]] 1 দ্বারা বাড়ান
- temp :=temp + s[i]
- যদি x <=maxLetters এর আকার হয়, তাহলে m[temp] 1 দ্বারা বাড়ান
- উত্তর :=0
- যদিও m-এ কিছু উপাদান থাকে, তারপর
- উত্তর :=উত্তরের সর্বোচ্চ এবং ith কী-মান জোড়ার মান
- উত্তর ফেরত দিন
উদাহরণ(C++)
আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxFreq(string s, int maxLetters, int minSize, int maxSize) {
unordered_map <string ,int > m;
for(int sz = minSize; sz <= minSize; sz++){
unordered_map <char, int> x;
string temp ="";
for(int i = 0; i < sz; i++){
x[s[i]]++;
temp += s[i];
}
for(int j = 0, i = sz; i < s.size(); i++, j++){
if(x.size() <= maxLetters){
m[temp]++;
}
x[temp[0]]--;
if(x[temp[0]] == 0)x.erase(temp[0]);
temp.erase(temp.begin(),temp.begin() + 1);
x[s[i]]++;
temp += s[i];
}
if(x.size() <= maxLetters){
m[temp]++;
}
}
int ans = 0;
unordered_map <string ,int > :: iterator i = m.begin();
while(i != m.end()){
ans = max (ans, i->second);
i++;
}
return ans;
}
};
main(){
Solution ob;
cout << (ob.maxFreq("aababcaab",2,3,4));
} ইনপুট
"aababcaab" 2 3 4
আউটপুট
2
