मान लीजिए हमारे पास एक स्ट्रिंग s है, हमें किसी भी सबस्ट्रिंग की अधिकतम घटनाओं की संख्या ढूंढनी है जो निम्नलिखित नियमों को पूरा करती है -
- सबस्ट्रिंग में विशिष्ट वर्णों की संख्या maxLetters से कम या बराबर होनी चाहिए।
- सबस्ट्रिंग का आकार minSize और maxSize की रेंज में समावेशी होना चाहिए।
यदि इनपुट इस प्रकार है - "aababcaab", maxLetters = 2, minSize = 3 और maxSize = 4, तो आउटपुट 2 होगा। सबस्ट्रिंग "aab" की मूल स्ट्रिंग में 2 घटनाएं हैं। यह शर्तों को पूरा करता है, 2 अद्वितीय अक्षर और आकार 3 (minSize और maxSize के बीच)।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे -
- एक मैप m परिभाषित करें
- sz के लिए minSize से maxSize तक की रेंज में
- x नामक एक मैप बनाएं, एक टेम्प स्ट्रिंग बनाएं, प्रारंभ में खाली
- i के लिए 0 से sz - 1 तक की रेंज में
- x[s[i]] को 1 से बढ़ाएं
- temp := temp + s[i]
- j 0 है, i के लिए sz से s के आकार - 1 तक की रेंज में, i और j को 1 से बढ़ाएं
- यदि x का आकार <= maxLetters है, तो m[temp] को 1 से बढ़ाएं
- x[temp[0]] को 1 से घटाएं
- यदि x[temp[0]] 0 है, तो temp[0] को x से डिलीट करें
- temp से पहले और दूसरे एलिमेंट को डिलीट करें
- x[s[i]] को 1 से बढ़ाएं
- temp := temp + s[i]
- यदि x का आकार <= maxLetters है, तो m[temp] को 1 से बढ़ाएं
- ans := 0
- जब तक मैप m में कुछ एलिमेंट्स हैं, तब तक
- ans := ans और i-वें की-वैल्यू पेयर के मान का मैक्स
- ans लौटाएं
उदाहरण (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
