सी ++ में सबसे लंबे समय तक दोहराए गए कैरेक्टर सबस्ट्रिंग के लिए स्वैप करें

मान लीजिए कि हमारे पास एक स्ट्रिंग टेक्स्ट है, इसलिए हमें स्ट्रिंग में दो वर्णों को स्वैप करने की अनुमति है। हमें दोहराए गए वर्णों के साथ सबसे लंबे समय तक सबस्ट्रिंग की लंबाई का पता लगाना है। इसलिए यदि इनपुट "अबाबा" जैसा है, तो परिणाम 3 होगा, जैसे कि हम पहले बी को अंतिम ए के साथ स्वैप करते हैं, या अंतिम बी को पहले ए के साथ स्वैप करते हैं, तो सबसे लंबे समय तक दोहराया जाने वाला चरित्र "आआ" होगा, इसलिए लंबाई है 3.

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक मानचित्र को परिभाषित करें, सेट करें:=1, j:=0, n:=पाठ का आकार, v:=0, x नामक एक सेट को परिभाषित करें, और m नामक एक अन्य मानचित्र बनाएं, m प्रत्येक वर्ण की आवृत्ति को धारण करेगा पाठ में।

• एक सेट करें:=* और बी:=*

• मेरे लिए 0 से n की सीमा में

  • cnt[text[i]] को 1 से बढ़ाएं

  • टेक्स्ट [i] को x में डालें

  • अगर cnt[text[i]] 2 है, तो

    • अगर एक * है। फिर a:=text[i], अन्यथा b :=text[i]

  • यदि a * नहीं है और b भी * नहीं है या x का आकार 2 से बड़ा है

    • cnt[text[j]] को 1 से कम करें

    • अगर cnt[text[j]] 1 है, तो

      • अगर टेक्स्ट [जे] एक है, तो एक सेट करें:=*, अन्यथा बी:=*

  • अगर cnt[text[j]] 0 है, तो टेक्स्ट [j] को x से हटा दें

  • ग्रेटर:=ए अगर सीएनटी [ए]> सीएनटी [बी], अन्यथा बी

  • यदि x का आकार 1 या m[अधिक] है - cnt[अधिक] गैर 0 है, तो

    • ret :=अधिकतम रिट, i – j + 1

  • अन्यथा रिट :=अधिकतम रिट, 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