सी ++ में एक सबस्ट्रिंग की घटनाओं की अधिकतम संख्या

मान लीजिए कि हमारे पास एक स्ट्रिंग s है, हमें निम्नलिखित नियमों को पूरा करने वाले किसी भी सबस्ट्रिंग की अधिकतम संख्या का पता लगाना है -

• सबस्ट्रिंग में अलग-अलग वर्णों की संख्या मैक्सलेटर्स से कम या उसके बराबर होनी चाहिए।
• सबस्ट्रिंग का आकार minSize और maxSize सहित रेंज में होना चाहिए।

तो अगर इनपुट इस तरह है - "आबाबकाब", मैक्सलेटर्स =2, मिनसाइज =3 और मैक्ससाइज =4, तो आउटपुट 2 होगा। सबस्ट्रिंग "आब" में मूल स्ट्रिंग में 2 घटनाएं होती हैं। यह शर्तों को पूरा करता है, 2 अद्वितीय अक्षर और आकार 3 (minSize और maxSize के बीच)।

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

• नक्शा परिभाषित करें मी
• sz के लिए minSize से maxSize तक
  • नक्शा x बनाएं, एक अस्थायी बनाएं, प्रारंभ में खाली
  • मैं के लिए 0 से sz - 1 की सीमा में
    • x[s[i]] को 1 से बढ़ाएं
    • अस्थायी:=अस्थायी + एस[i]
  • के लिए j 0 है, i श्रेणी sz से s-1 के आकार तक, i और j को 1 से बढ़ाएँ
    • यदि x <=maxLetters का आकार है, तो m[temp] को 1 से बढ़ा दें
    • x[temp[0]] 1 से घटाएं
    • यदि x[temp[0]] 0 है, तो x से temp[0] हटा दें
    • अस्थायी के पहले और दूसरे तत्व को अस्थायी से ही हटाएं
    • x[s[i]] को 1 से बढ़ाएं
    • अस्थायी:=अस्थायी + एस[i]
  • यदि x <=maxLetters का आकार है, तो m[temp] को 1 से बढ़ा दें
• उत्तर:=0
• जबकि मानचित्र m में कुछ तत्व हैं, तब
  • उत्तर :=अधिकतम उत्तर और ith कुंजी-मान युग्म का मान
• वापसी उत्तर

उदाहरण(C++)

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int maxFreq(string s, int maxLetters, int minSize, int maxSize) {
      unordered_map <string ,int > m;
      for(int sz = minSize; sz <= minSize; sz++){
         unordered_map <char, int> x;
         string temp ="";
         for(int i = 0; i < sz; i++){
            x[s[i]]++;
            temp += s[i];
         }
         for(int j = 0, i = sz; i < s.size(); i++, j++){
            if(x.size() <= maxLetters){
               m[temp]++;
            }
            x[temp[0]]--;
            if(x[temp[0]] == 0)x.erase(temp[0]);
            temp.erase(temp.begin(),temp.begin() + 1);
            x[s[i]]++;
            temp += s[i];
         }
         if(x.size() <= maxLetters){
            m[temp]++;
         }
      }
      int ans = 0;
      unordered_map <string ,int > :: iterator i = m.begin();
      while(i != m.end()){
         ans = max (ans, i->second);
         i++;
      }
      return ans;
   }
};
main(){
   Solution ob;
   cout << (ob.maxFreq("aababcaab",2,3,4));
}

इनपुट

"aababcaab"
2
3
4

आउटपुट

2