Hoán đổi để có chuỗi ký tự lặp lại lâu nhất trong C ++

Giả sử chúng ta có một văn bản chuỗi, vì vậy chúng ta được phép hoán đổi hai trong số các ký tự trong chuỗi. Chúng ta phải tìm độ dài của chuỗi con dài nhất với các ký tự lặp lại. Vì vậy, nếu đầu vào là “ababa”, thì kết quả sẽ là 3, như thể chúng ta hoán đổi b đầu tiên với a cuối cùng hoặc b cuối cùng với a đầu tiên, thì ký tự lặp lại dài nhất sẽ là “aaa”, vì vậy độ dài là 3.

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

• Xác định bản đồ cnt, đặt ret:=1, j:=0, n:=kích thước của văn bản, v:=0, xác định một tập hợp có tên là x và tạo một bản đồ khác có tên là m, m sẽ giữ tần số của mỗi ký tự trong văn bản.

• đặt a:=* và b:=*

• cho tôi trong phạm vi từ 0 đến n

  • tăng cnt [text [i]] lên 1

  • chèn văn bản [i] vào x

  • nếu cnt [text [i]] là 2 thì

    • nếu a là *. thì a:=text [i], ngược lại b:=text [i]

  • nếu a không phải là * và b cũng không phải là * hoặc kích thước của x lớn hơn 2

    • giảm cnt [text [j]] 1

    • nếu cnt [text [j]] là 1 thì

      • nếu text [j] là a, thì đặt a:=*, ngược lại là b:=*

  • nếu cnt [text [j]] là 0, thì hãy xóa text [j] khỏi x

  • lớn hơn:=a nếu cnt [a]> cnt [b], nếu không thì b

  • nếu kích thước của x là 1 hoặc m [lớn hơn] - cnt [lớn hơn] khác 0 thì

    • ret:=max của ret, i - j + 1

  • nếu không thì ret:=max of ret, i - j

• trả lại ret.

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

Ví dụ

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

Đầu vào

"ababa"

Đầu ra

3