मान लीजिए हमारे पास एक स्ट्रिंग s है, और हमें दिए गए स्ट्रिंग (केवल लोअरकेस अक्षरों से युक्त) के सबसे लंबे उपस्ट्रिंग T की लंबाई ढूंढनी है जैसे कि T में प्रत्येक वर्ण कम से कम k बार प्रकट होता है। इसलिए यदि स्ट्रिंग "ababbc" है और k = 2, तो आउटपुट 3 होगा और सबसे लंबा उपस्ट्रिंग "ababb" होगा, क्योंकि वहां दो 'a' और तीन 'b' हैं।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- longestSubstring() नामक एक पुनरावर्ती फ़ंक्शन बनाएं, यह स्ट्रिंग s और आकार k लेता है
- यदि k = 1, तो स्ट्रिंग का आकार लौटाएं
- यदि स्ट्रिंग का आकार < k, तो 0 लौटाएं
- आकार 26 की एक सरणी c बनाएं, और इसे -1 से भरें
- n := स्ट्रिंग का आकार
- i को 0 से n तक की रेंज में
- यदि c[s[i] - 'a'] = -1, तो c[s[i] - 'a'] := 1, अन्यथा c[s[i] - 'a'] को 1 से बढ़ाएं
- badChar := '*'
- i को 0 से 25 तक की रेंज में
- यदि c[i] -1 नहीं है और c[i] < k, तो badChar := i + 'a' और लूप से बाहर निकलें
- यदि badChar = '*', तो n लौटाएं
- v := मूल स्ट्रिंग को badChar का उपयोग करके विभाजित करके स्ट्रिंग्स की एक अन्य सरणी
- ans := 0
- i को 0 से v के आकार तक की रेंज में
- ans := ans और longestSubstring(v[i], k) का अधिकतम
- ans लौटाएं
उदाहरण (C++)
बेहतर समझ के लिए निम्नलिखिक कार्यान्वयन देखें -
#include <bits/stdc++.h> using namespace std; class Solution { public: vector <string> splitString(string s, char x){ string temp = ""; vector <string> res; for(int i = 0; i < s.size(); i++){ if(s[i] == x){ if(temp.size())res.push_back(temp); temp = ""; } else temp += s[i]; } if(temp.size())res.push_back(temp); return res; } int longestSubstring(string s, int k) { if(k == 1)return s.size(); if(s.size() < k )return 0; vector <int> cnt(26, -1); int n = s.size(); for(int i = 0; i < n; i++){ if(cnt[s[i] - 'a'] == -1) cnt[s[i] - 'a'] = 1; else cnt[s[i] - 'a']++; } char badChar = '*'; for(int i = 0; i < 26; i++){ if(cnt[i] != -1 && cnt[i] < k){ badChar = i + 'a'; break; } } if(badChar == '*')return n; vector <string> xx = splitString(s, badChar); int ans = 0; for(int i = 0; i < xx.size(); i++)ans = max(ans, longestSubstring(xx[i], k)); return ans; } }; main(){ Solution ob; cout << ob.longestSubstring("ababbc", 2); }इनपुट
"ababbc" 2
आउटपुट
5