การแทนที่อักขระซ้ำที่ยาวที่สุดใน C++

สมมติว่าเราได้ให้สตริง s ที่ประกอบด้วยตัวพิมพ์ใหญ่เท่านั้น เราสามารถดำเนินการได้มากที่สุด k การดำเนินการกับสตริงนั้น ในการดำเนินการเดียว เราสามารถเลือกอักขระใดๆ ของสตริงและเปลี่ยนเป็นอักษรตัวพิมพ์ใหญ่อื่นๆ ได้ เราต้องหาความยาวของสตริงย่อยที่ยาวที่สุดที่มีตัวอักษรซ้ำกันทั้งหมดที่เราจะได้รับหลังจากดำเนินการข้างต้น ดังนั้นหากอินพุตมีลักษณะดังนี้:“ABAB” และ k =2 ผลลัพธ์จะเป็น 4 เนื่องจาก ‘A’ สองตัวที่มี ‘B’ สองตัวหรือในทางกลับกัน

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• maxCount :=0, ans :=0 and n :=ขนาดของสตริง s
• สร้างอาร์เรย์ cnt ขนาด 26 และ j :=0
• สำหรับ i :=0 ถึง n – 1
  • เพิ่ม ct[s[i] – 'A'] ขึ้น 1
  • maxCount :=max ของ maxCount, นับ[s[i] – 'A']
  • ในขณะที่ j <=i และ i – j + 1 – maxCount> k ทำ
    • ลด ct[s[j] – ‘A’]
    • เพิ่ม j ขึ้น 1
  • ans :=สูงสุดของ ans, 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

ผลลัพธ์

4