मान लीजिए हमारे पास एक स्ट्रिंग s है; हमें सबसे लंबे सबस्ट्रिंग t की लंबाई ढूंढनी है जिसमें अधिकतम 2 विशिष्ट कैरेक्टर्स हों।
इसलिए, यदि इनपुट है "eceba", तो आउटपुट 3 होगा क्योंकि t "ece" है जिसकी लंबाई 3 है।
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:
एक फ़ंक्शन lengthOfLongestSubstringKDistinct() परिभाषित करें, जो s, k लेगा,
ans := 0
एक मैप m परिभाषित करें
n := s का आकार, x := 0
j := 0, i := 0 से शुरू करें, जब j < n, j बढ़ाते हुए, करें -
(m[s[j]] को 1 से बढ़ाएं)
यदि m[s[j]], 1 के समान है, तो -
(x को 1 से बढ़ाएं)
जब (x > k और i <= j), करें -
(m[s[i]] को 1 से घटाएं)
यदि m[s[i]], 0 के समान है, तो -
(x को 1 से घटाएं)
(i को 1 से बढ़ाएं)
ans := max(ans, j - i + 1)
ans लौटाएं
मुख्य विधि से निम्न करें
lengthOfLongestSubstringKDistinct(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
