ধরুন আমাদের একটি স্ট্রিং টেক্সট আছে, তাই আমরা স্ট্রিং এর দুটি অক্ষর অদলবদল করতে পারি। আমাদের বারবার অক্ষর সহ দীর্ঘতম সাবস্ট্রিং এর দৈর্ঘ্য খুঁজে বের করতে হবে। সুতরাং যদি ইনপুটটি "আবাবা" এর মত হয়, তাহলে ফলাফলটি হবে 3, যেমন আমরা শেষ a দিয়ে প্রথম b অদলবদল করি, অথবা শেষ b প্রথম a দিয়ে, তাহলে দীর্ঘতম পুনরাবৃত্তি অক্ষরটি হবে "aaa", তাই দৈর্ঘ্য হবে 3.
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি মানচিত্র cnt সংজ্ঞায়িত করুন, ret :=1, j :=0, n :=পাঠ্যের আকার, v :=0, x নামে একটি সেট সংজ্ঞায়িত করুন এবং m নামে আরেকটি মানচিত্র তৈরি করুন, m প্রতিটি অক্ষরের ফ্রিকোয়েন্সি ধরে রাখবে পাঠ্যে৷
৷ -
a :=* এবং b :=*
সেট করুন -
আমি 0 থেকে n
পরিসরে-
cnt[text[i]] 1
দ্বারা বাড়ান -
x
-এ পাঠ্য[i] সন্নিবেশ করান -
যদি cnt[text[i]] 2 হয়, তাহলে
-
যদি a হয় *। তারপর a :=text[i], অন্যথায় b :=text[i]
-
-
যদি a * না হয় এবং bও * না হয় বা x এর আকার 2 এর বেশি হয়
-
cnt[text[j]] 1
কমিয়ে দিন -
যদি cnt[text[j]] 1 হয়, তাহলে
-
যদি টেক্সট [j] a হয়, তাহলে a :=* সেট করুন, অন্যথায় b :=*
-
-
-
যদি cnt[text[j]] 0 হয়, তাহলে x
থেকে text[j] মুছে দিন -
বৃহত্তর :=a if cnt[a]> cnt[b], অন্যথায় b
-
যদি x এর আকার 1 বা m[বৃহত্তর] হয় - cnt[বৃহত্তর] অ 0 হয়, তাহলে
-
ret :=ret এর সর্বোচ্চ, i – j + 1
-
-
অন্যথায় ret :=ret এর সর্বোচ্চ, i – j
-
-
রিটার্ন রিটার্ন।
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxRepOpt1(string text) {
int ret = 1;
map <char, int> cnt;
int j = 0;
int n = text.size();
int v = 0;
set <char> x;
map <char, int> m;
for(int i = 0; i < text.size(); i++)m[text[i]]++;
char a = '*', b ='*';
for(int i = 0; i < n; i++){
cnt[text[i]]++;
x.insert(text[i]);
if(cnt[text[i]] == 2){
if(a == '*'){
a = text[i];
}else{
b = text[i];
}
}
while(a != '*' && b != '*' || x.size() > 2){
cnt[text[j]]--;
if(cnt[text[j]] == 1) {
if(text[j] == a) {
a ='*';
}else{
b = '*';
}
}
if(cnt[text[j]] == 0) x.erase(text[j]);
j++;
}
char greater = cnt[a] > cnt[b] ? a : b;
if(x.size() == 1 || m[greater] - cnt[greater]){
ret = max(ret, i - j + 1);
}else{
ret = max(ret, i - j);
}
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.maxRepOpt1("ababa"));
} ইনপুট
"ababa"
আউটপুট
3
