สลับสำหรับสตริงย่อยอักขระที่ยาวที่สุดใน C++

สมมติว่าเรามีข้อความสตริง ดังนั้นเราจึงสามารถสลับอักขระสองตัวในสตริงได้ เราต้องหาความยาวของสตริงย่อยที่ยาวที่สุดด้วยอักขระที่ซ้ำกัน ดังนั้นหากอินพุตเป็นเหมือน "ababa" ผลลัพธ์จะเป็น 3 ราวกับว่าเราสลับ b ตัวแรกกับ a สุดท้าย หรือ b สุดท้ายกับ a ตัวแรก จากนั้นอักขระที่ทำซ้ำที่ยาวที่สุดจะเป็น "aaa" ดังนั้นความยาวจึงเท่ากับ 3.

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

• กำหนดแผนที่ cnt ตั้งค่า ret :=1 j :=0, n :=ขนาดของข้อความ v :=0 กำหนดชุดที่เรียกว่า x และสร้างแผนที่อื่นที่เรียกว่า m m จะเก็บความถี่ของอักขระแต่ละตัว ในข้อความ

• ตั้งค่า a :=* และ b :=*

• สำหรับฉันอยู่ในช่วง 0 ถึง n

  • เพิ่ม cnt[text[i]] ขึ้น 1

  • แทรกข้อความ[i] ลงใน x

  • ถ้า cnt[text[i]] เป็น 2 แล้ว

    • ถ้า a คือ * แล้ว a :=text[i] หรือ b :=text[i]

  • ถ้า a ไม่ใช่ * และ b ไม่ใช่ * หรือขนาดของ x มากกว่า 2

    • ลด cnt[text[j]] ลง 1

    • ถ้า cnt[text[j]] คือ 1 แล้ว

      • ถ้า text[j] เป็น a ให้ตั้งค่า a :=* มิฉะนั้น b :=*

  • ถ้า cnt[text[j]] เป็น 0 ให้ลบ text[j] ออกจาก x

  • มากกว่า :=a if cnt[a]> cnt[b] มิฉะนั้น b

  • ถ้าขนาดของ x เป็น 1 หรือ m[มากกว่า] – cnt[ยิ่งใหญ่] ไม่ใช่ 0 ดังนั้น

    • ret :=สูงสุดของ ret, i – j + 1

  • มิฉะนั้น ret :=สูงสุดของ ret, i – j

• รีเทิร์น.

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

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

อินพุต

"ababa"

ผลลัพธ์

3