Thay thế ký tự lặp lại lâu nhất trong C ++

Giả sử chúng ta đã cho một chuỗi s chỉ gồm các chữ cái viết hoa, chúng ta có thể thực hiện nhiều nhất k phép toán trên chuỗi đó. Trong một thao tác, chúng ta có thể chọn bất kỳ ký tự nào của chuỗi và thay đổi nó thành bất kỳ ký tự hoa nào khác. Chúng ta phải tìm độ dài của chuỗi con dài nhất chứa tất cả các chữ cái lặp lại mà chúng ta có thể nhận được sau khi thực hiện các thao tác trên. Vì vậy, nếu đầu vào là:“ABAB” và k =2, thì đầu ra sẽ là 4. Điều này là do hai ‘A’s với hai‘ B’s hoặc ngược lại.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• maxCount:=0, ans:=0 và n:=kích thước của chuỗi s
• tạo một mảng cnt có kích thước 26 và j:=0
• for i:=0 to n - 1
  • tăng cnt [s [i] - ‘A’] thêm 1
  • maxCount:=max của maxCount, count [s [i] - ‘A’]
  • while j <=i and i - j + 1 - maxCount> k, do
    • giảm cnt [s [j] - ‘A’]
    • tăng j lên 1
  • ans:=max of ans, i - j + 1
• trả lại ans

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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);
}

Đầu vào

"ABAB"
2

Đầu ra

4