এই সমস্যায় একটি আপারকেস স্ট্রিং s এবং ইন্টিজার k দেওয়া থাকলে, সর্বোচ্চ kটি ক্যারেক্টার পরিবর্তন করে সবচেয়ে লম্বা সাবস্ট্রিং বানাতে হবে যাতে সেটির সব ক্যারেক্টার একই হয়।
উদাহরণ: s="ABAB", k=2 -> আউটপুট 4 (দুটি A কে B বা দুটি B কে A করে AAAA বা BBBB বানানো যায়)।
সমাধানের পদ্ধতি (Sliding Window)
- উইন্ডো
[left, right]। count[26]= উইন্ডোতে প্রতিটি ক্যারেক্টারের ফ্রিকোয়েন্সি।maxCount= উইন্ডোতে সর্বোচ্চ ফ্রিকোয়েন্সি।- উইন্ডো আকার -
maxCount= পরিবর্তন করতে হবে এমন ক্যারেক্টারগুলো। এটিk-এর চেয়ে বড় হলে উইন্ডো সঙ্কুচিত করুন (left++)। - আনসার = max(আনসার, উইন্ডো আকার)।
উদাহরণ (C++)
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int characterReplacement(string s, int k) {
vector<int> count(26, 0);
int left = 0, maxCount = 0, ans = 0;
for (int right = 0; right < s.size(); right++) {
count[s[right] - 'A']++;
maxCount = max(maxCount, count[s[right] - 'A']);
while (right - left + 1 - maxCount > k) {
count[s[left] - 'A']--;
left++;
}
ans = max(ans, right - left + 1);
}
return ans;
}
};
int main() {
Solution ob;
cout << ob.characterReplacement("ABAB", 2);
return 0;
}
ইনপুট
"ABAB" 2
আউটপুট
4
