Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

अधिकतम K विशिष्ट वर्णों वाला सबसे लंबा सबस्ट्रिंग - C++


मान लीजिए हमारे पास एक स्ट्रिंग है; हमें सबसे लंबे सबस्ट्रिंग 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

  1. C++ में सबसे अधिक पानी वाला कंटेनर C++ में सबसे अधिक पानी वाला कंटेनर

    हमें कंटेनर की दीवारों की ऊंचाई की एक सरणी दी गई है। लक्ष्य वह कंटेनर ढूंढना है जो पानी की अधिकतम मात्रा धारण कर सके। चूंकि दीवारों की ऊंचाई सरणी के तत्व हैं, उनके बीच की दूरी को दो दीवारों के बीच की चौड़ाई माना जाता है। उदाहरण के लिए ऊंचाई Arr[i] और Arr[j] की दीवारों के बीच j-i चौड़ाई होती है (0<=i

  1. - C++ में सबस्ट्रिंग को दूसरी सबस्ट्रिंग से रिप्लेस करना

    यहां हम देखेंगे कि सबस्ट्रिंग को दूसरी सबस्ट्रिंग से कैसे रिप्लेस करें। यह स्ट्रिंग के उस हिस्से को रिप्लेस करता है जो कैरेक्टर पोजीशन pos से शुरू होता है और len कैरेक्टर्स तक फैला होता है। रिप्लेस फंक्शन की संरचना नीचे दी गई है: string& replace (size_t pos, size_t len, const string& str, s

  1. - पायथन में k विशिष्ट वर्णों वाले सबसे लंबे सबस्ट्रिंग की लंबाई खोजने का प्रोग्राम

    मान लीजिए हमारे पास एक संख्या k और एक स्ट्रिंग s है, हमें उस सबसे लंबे सबस्ट्रिंग का आकार ढूंढना है जिसमें अधिकतम k विशिष्ट वर्ण हों।उदाहरण के लिए, यदि इनपुट k = 3 और s = kolkata है, तो आउटपुट 4 होगा, क्योंकि 3 विशिष्ट वर्णों वाले दो सबसे लंबे सबस्ट्रिंग kolk और kata हैं, जिनकी लंबाई 4 है।समाधान दृष