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

C++ में Longest Repeating Character Replacement


मान लीजिए हमारे पास एक स्ट्रिंग s दी गई है जिसमें केवल बड़े अक्षर (uppercase letters) होते हैं, हम उस स्ट्रिंग पर अधिकतम k ऑपरेशन कर सकते हैं। एक ऑपरेशन में, हम स्ट्रिंग के किसी भी वर्ण का चयन कर सकते हैं और उसे किसी अन्य बड़े अक्षर में बदल सकते हैं। हमें उपरोक्त ऑपरेशन करने के बाद सभी दोहराव वाले अक्षरों वाले सबसे लंबे उपस्ट्रिंग (sub-string) की लंबाई ढूंढनी है। इसलिए यदि इनपुट "ABAB" जैसा है और k = 2, तो आउटपुट 4 होगा। ऐसा इसलिए क्योंकि दो 'A' दो 'B' के साथ या इसके विपरीत।

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

  • maxCount := 0, ans := 0 और n := स्ट्रिंग s का आकार
  • आकार 26 की एक सरणी cnt बनाएं, और j := 0
  • i := 0 से n - 1 तक
    • cnt[s[i] - 'A'] को 1 से बढ़ाएं
    • maxCount := maxCount, count[s[i] - 'A'] का अधिकतम
    • जब तक j <= i और i - j + 1 - maxCount > k, करें
      • cnt[s[j] - 'A'] घटाएं
      • j को 1 से बढ़ाएं
    • ans := ans, i - j + 1 का अधिकतम
  • ans लौटाएं

उदाहरण (C++)

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

#include <bits/stdc++.h> using namespace std; class Solution { public:    int characterReplacement(string s, int k) {       int maxCount = 0;       int ans = 0;       int n = s.size();       vector <int> cnt(26);       int j = 0;       for(int i = 0; i < n; i++){          cnt[s[i] - 'A']++;          maxCount = max(maxCount, cnt[s[i] - 'A']);          while(j <= i && i - j + 1 - maxCount > k){             --cnt[s[j] - 'A'];             j++;          }          ans = max(ans, i - j + 1);       }       return ans;    } }; main(){    Solution ob;    cout << ob.characterReplacement("ABAB", 2); }

इनपुट

"ABAB" 2

आउटपुट

4

  1. - C++ में प्रत्येक वर्ण प्रतिस्थापन क्वेरी के बाद पैलिंड्रोम की जांच

    मान लीजिए हमारे पास एक स्ट्रिंग और क्वेरी का समुच्चय Q है। प्रत्येक क्वेरी में पूर्णांकों i और j का एक जोड़ा होता है। और एक और वर्ण c। हमें इंडेक्स i और j पर वर्णों को नए वर्ण c से बदलना है। और बताना है कि स्ट्रिंग पैलिंड्रोम है या नहीं। मान लीजिए एक स्ट्रिंग AXCDCMP जैसी है, यदि हम (1, 5, B) जैसी ए

  1. - C++ में string at() फंक्शन

    इस खंड में, हम देखेंगे कि C++ में at() फंक्शन क्या है। at() फंक्शन का उपयोग दिए गए स्थान पर वर्ण को एक्सेस करने के लिए किया जाता है। इस प्रोग्राम में, हम at() फंक्शन का उपयोग करके प्रत्येक वर्ण के माध्यम से पुनरावृति करेंगे और उन्हें अलग-अलग लाइनों में प्रिंट करेंगे। उदाहरण कोड #include<iostrea

  1. - C++ में strpbrk() फ़ंक्शन

    strpbrk() फ़ंक्शन C++ स्ट्रिंग फ़ंक्शन जो दो स्ट्रिंग्स लेता है और स्ट्रिंग1 में स्ट्रिंग2 के किसी भी अक्षर की पहली घटना ढूंढता है। मिलने पर उस अक्षर का पॉइंटर लौटाता है, अन्यथा NULL। टर्मिनेटिंग NULL अक्षर के लिए लागू नहीं। सिंटैक्स char* strpbrk(const char* str1, const char* str2) C++ प्रोग्राम