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