मान लीजिए हमारे पास एक स्ट्रिंग टेक्स्ट है, इसलिए हमें स्ट्रिंग में दो कैरेक्टर्स को स्वैप करने की अनुमति है। हमें दोहराए गए कैरेक्टर्स वाले सबसे लंबे सबस्ट्रिंग की लंबाई ढूंढनी है। इसलिए अगर इनपुट "ababa" है, तो परिणाम 3 होगा, क्योंकि अगर हम पहले b को अंतिम a से स्वैप करते हैं, या अंतिम b को पहले a से, तो सबसे लंबा दोहराया गया कैरेक्टर "aaa" होगा, इसलिए लंबाई 3 है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:
cnt नामक एक मैप परिभाषित करें, ret := 1, j := 0, n := टेक्स्ट का आकार, v := 0, x नामक एक सेट परिभाषित करें, और m नामक एक और मैप बनाएं, m टेक्स्ट में प्रत्येक कैरेक्टर की आवृत्ति रखेगा।
a := * और b := * सेट करें
i को 0 से n तक रेंज में लिए:
cnt[text[i]] को 1 से बढ़ाएं
text[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 से हटाएं
greater := a यदि cnt[a] > cnt[b], अन्यथा b
यदि x का आकार 1 है या m[greater] - cnt[greater] शून्येतर है, तो
ret := ret का अधिकतम, i - j + 1
अन्यथा ret := ret का अधिकतम, i - j
ret लौटाएं।
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
उदाहरण
#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
