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

मान लीजिए कि हमारे पास एक स्ट्रिंग है; हमें सबसे लंबे सबस्ट्रिंग T की लंबाई की गणना करनी होगी जिसमें अधिकतम k अलग-अलग वर्ण हों।

इसलिए, यदि इनपुट s ="eceba", k =2 जैसा है, तो आउटपुट 3 होगा क्योंकि T "ece" है जिसकी लंबाई 3 है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• उत्तर :=0

• एक नक्शा परिभाषित करें मी

• n :=s का आकार

• एक्स:=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 से घटाएं)

    • (i 1 से बढ़ाएँ)

  • उत्तर :=अधिकतम उत्तर और (j - i + 1)

• वापसी उत्तर

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

#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