ধরুন আমাদের একটি স্ট্রিং s আছে, এবং আমাদের সেই প্রদত্ত স্ট্রিংটির দীর্ঘতম সাবস্ট্রিং T-এর দৈর্ঘ্য খুঁজে বের করতে হবে (শুধুমাত্র ছোট হাতের অক্ষর নিয়ে গঠিত) যাতে T-এর প্রতিটি অক্ষর কম দেখা না যায় k বার থেকে তাই যদি স্ট্রিংটি "ababbc" এবং k =2 হয়, তাহলে আউটপুট হবে 3 এবং দীর্ঘতম সাবস্ট্রিং হবে "ababb", কারণ দুটি a's এবং তিনটি b's আছে।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- একটি পুনরাবৃত্ত ফাংশন তৈরি করুন যার নাম longestSubstring(), এটি স্ট্রিং s এবং k আকার নেয়
- যদি k =1 হয়, তাহলে স্ট্রিংটির আকার ফেরত দিন
- যদি স্ট্রিং এর আকার
- 26 আকারের একটি অ্যারে c তৈরি করুন এবং এটি -1 দিয়ে পূরণ করুন
- n :=স্ট্রিংয়ের আকার
- আমি 0 থেকে n
- পরিসরে
- যদি c[s[i] – 'a'] =-1, তাহলে c[s[i] – 'a'] :=1, অন্যথায় c[s[i] – 'a'] 1 দ্বারা বাড়ান
- খারাপচার :=‘*’
- আমি 0 থেকে 25 রেঞ্জের জন্য
- যদি c[i] -1 এবং c[i]
- যদি badChar ='*', তাহলে n ফেরত দিন
- v :=badChar ব্যবহার করে মূল স্ট্রিংকে বিভক্ত করে স্ট্রিংয়ের আরেকটি অ্যারে
- উত্তর :=0
- আমি 0 থেকে v
- এর পরিসরে
- উত্তর :=উত্তরের সর্বোচ্চ এবং দীর্ঘতম সাবস্ট্রিং(v[i], k)
- উত্তর ফেরত দিন
উদাহরণ(C++)
আসুন আরও ভালোভাবে বোঝার জন্য নিচের বাস্তবায়ন দেখি −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector <string> splitString(string s, char x){
string temp = "";
vector <string> res;
for(int i = 0; i < s.size(); i++){
if(s[i] == x){
if(temp.size())res.push_back(temp);
temp = "";
}
else temp += s[i];
}
if(temp.size())res.push_back(temp);
return res;
}
int longestSubstring(string s, int k) {
if(k == 1)return s.size();
if(s.size() < k )return 0;
vector <int> cnt(26, -1);
int n = s.size();
for(int i = 0; i < n; i++){
if(cnt[s[i] - 'a'] == -1) cnt[s[i] - 'a'] = 1;
else cnt[s[i] - 'a']++;
}
char badChar = '*';
for(int i = 0; i < 26; i++){
if(cnt[i] != -1 && cnt[i] < k){
badChar = i + 'a';
break;
}
}
if(badChar == '*')return n;
vector <string> xx = splitString(s, badChar);
int ans = 0;
for(int i = 0; i < xx.size(); i++)ans = max(ans, longestSubstring(xx[i], k));
return ans;
}
};
main(){
Solution ob;
cout << ob.longestSubstring("ababbc", 2);
} ইনপুট
৷"ababbc" 2
আউটপুট
5
