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

C++ में Longest Substring with At Least K Repeating Characters


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

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

    मान लीजिए हमारे पास एक लोअरकेस स्ट्रिंग s है, हमें उस सबसे लंबे सबस्ट्रिंग की लंबाई ढूंढनी है जो s में कम से कम दो बार आता है। यदि ऐसा कोई स्ट्रिंग नहीं मिलता, तो 0 लौटाएं। उदाहरण के लिए, यदि इनपुट है s = abdgoalputabdtypeabd, तो आउटपुट 3 होगा, क्योंकि सबसे लंबा सबस्ट्रिंग जो एक से अधिक बार आता है व

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

    मान लीजिए हमारे पास एक स्ट्रिंग है हमें सबसे लंबा संभव सबस्ट्रिंग लौटाना है जिसमें ठीक k संख्या में अद्वितीय वर्ण हों, यदि सबसे लंबी संभव लंबाई के एक से अधिक सबस्ट्रिंग हैं, तो उनमें से कोई भी लौटाएं।तो, यदि इनपुट s = ppqprqtqtqt, k = 3 जैसा है, तो आउटपुट rqtqtqt होगा क्योंकि इसकी लंबाई 7 है।इसे हल

  1. - पायथन में बिना दोहराव वाले वर्णों का सबसे लंबा सबस्ट्रिंग

    मान लीजिए हमारे पास एक स्ट्रिंग है। हमें बिना वर्णों को दोहराए सबसे लंबा सबस्ट्रिंग ढूंढना है। इसलिए यदि स्ट्रिंग ABCABCBB जैसी है, तो परिणाम 3 होगा, क्योंकि लंबाई 3 का एक सबस्ट्रिंग है जो दोहरा रहा है। वह है ABC। इसे हल करने के लिए, हम इन चरणों का पालन करेंगे: i := 0, j := 0 सेट करें, जानकारी स्