C++ এ দীর্ঘতম পুনরাবৃত্তিকারী অক্ষর প্রতিস্থাপন

ধরুন আমরা একটি স্ট্রিং s দিয়েছি যেটিতে শুধুমাত্র বড় হাতের অক্ষর রয়েছে, আমরা সেই স্ট্রিংটিতে সর্বাধিক k অপারেশন করতে পারি। একটি অপারেশনে, আমরা স্ট্রিংয়ের যেকোনো অক্ষর নির্বাচন করতে পারি এবং অন্য কোনো বড় হাতের অক্ষরে পরিবর্তন করতে পারি। উপরের ক্রিয়াকলাপগুলি সম্পাদন করার পরে আমরা যে সমস্ত পুনরাবৃত্ত অক্ষরগুলি পেতে পারি তা আমাদেরকে দীর্ঘতম সাব-স্ট্রিংটির দৈর্ঘ্য খুঁজে বের করতে হবে। সুতরাং ইনপুট যদি হয়:“ABAB” এবং k =2, তাহলে আউটপুট হবে 4। এর কারণ হল দুটি ‘A’ এর সাথে দুটি ‘B’ বা বিপরীতে।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

maxCount :=0, ans :=0 এবং n :=স্ট্রিং এর আকার
26 সাইজের cnt এবং j :=0 এর একটি অ্যারে তৈরি করুন
এর জন্য i :=0 থেকে n – 1
- cnt[s[i] – 'A'] 1 দ্বারা বাড়ান
- maxCount :=maxCount এর সর্বোচ্চ, গণনা[s[i] – 'A']
- যখন j <=i এবং i – j + 1 – maxCount> k, do
  - cnt[s[j] – 'A']
  - j 1 দ্বারা বাড়ান
- উত্তর :=উত্তরের সর্বোচ্চ, i – j + 1
উত্তর ফেরত দিন

উদাহরণ(C++)

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int characterReplacement(string s, int k) {
      int maxCount = 0;
      int ans = 0;
      int n = s.size();
      vector <int> cnt(26);
      int j = 0;
      for(int i = 0; i < n; i++){
         cnt[s[i] - 'A']++;
         maxCount = max(maxCount, cnt[s[i] - 'A']);
         while(j <= i && i - j + 1 - maxCount > k){
            --cnt[s[j] - 'A'];
            j++;
         }
         ans = max(ans, i - j + 1);
      }
      return ans;
   }
};
main(){
   Solution ob;
   cout << ob.characterReplacement("ABAB", 2);
}

ইনপুট

"ABAB"
2