मान लीजिए कि हमारे पास एक स्ट्रिंग s है; हमें सबसे लंबे सबस्ट्रिंग t की लंबाई ज्ञात करनी होगी जिसमें अधिकतम 2 अलग-अलग वर्ण हों।
इसलिए, यदि इनपुट "eceba" जैसा है, तो आउटपुट 3 होगा क्योंकि t "ece" है जिसकी लंबाई 3 है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
एक फ़ंक्शन को परिभाषित करें lengthOfLongestSubstringKDistinct(), इसमें s, k,
लगेगा -
उत्तर:=0
-
एक नक्शा परिभाषित करें मी
-
n :=s का आकार, x :=0
-
प्रारंभ करने के लिए j :=0, i :=0, जब j
-
(m[s[j]] 1 से बढ़ाएं)
-
अगर m[s[j]] 1 के समान है, तो -
-
(x 1 से बढ़ाएँ)
-
-
जबकि (x> k और i <=j), करते हैं -
-
(मी [s[i]] 1 से घटाएं)
-
अगर m[s[i]] 0 के समान है, तो -
-
(x 1 से घटाएं)
-
-
(मैं 1 से बढ़ाइए)
-
-
उत्तर:=अधिकतम उत्तर और j - i + 1
-
-
वापसी उत्तर
-
मुख्य विधि से निम्न कार्य करें
-
वापसी की लंबाईOfLongestSubstringKDistinct(s, 2)
उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int lengthOfLongestSubstringKDistinct(string s, int k){
int ans = 0;
unordered_map<char, int> m;
int n = s.size();
int x = 0;
for (int j = 0, i = 0; j < n; j++) {
m[s[j]]++;
if (m[s[j]] == 1)
x++;
while (x > k && i <= j) {
m[s[i]]--;
if (m[s[i]] == 0)
x--;
i++;
}
ans = max(ans, j - i + 1);
}
return ans;
}
int lengthOfLongestSubstringTwoDistinct(string s){
return lengthOfLongestSubstringKDistinct(s, 2);
}
};
main(){
Solution ob;
cout << (ob.lengthOfLongestSubstringTwoDistinct("eceba"));
} इनपुट
"eceba"
आउटपुट
3
