सी ++ में कॉनटेनेटेड बाइनरी स्ट्रिंग में अधिकतम लगातार शून्य

मान लीजिए कि हमारे पास लंबाई n की एक बाइनरी स्ट्रिंग है, एक अन्य मान जैसे k दिया गया है। हमें बाइनरी स्ट्रिंग को k बार जोड़ना होगा। फिर हमें संयोजित स्ट्रिंग में लगातार 0s की अधिकतम संख्या ज्ञात करनी होगी। मान लीजिए कि बाइनरी स्ट्रिंग "0010010" है, और k =2 है, तो स्ट्रिंग को k बार संयोजित करने के बाद, यह "00100100010010" होगा। तो लगातार 0s की अधिकतम संख्या 3 है।

दृष्टिकोण सरल है। यदि संख्या में सभी 0 हैं, तो उत्तर n * k होगा। यदि स्ट्रिंग में एक है, तो परिणाम या तो स्ट्रिंग के एक विकल्प की अधिकतम लंबाई होगी, जिसमें सभी 0s होंगे, या केवल 0s वाले स्ट्रिंग के अधिकतम उपसर्ग की लंबाई और अधिकतम प्रत्यय की लंबाई के बीच का योग होगा। एक स्ट्रिंग जिसमें केवल 0s होते हैं।

एल्गोरिदम

max_zero_count (str, n, k) −

Begin
total := 0
len := 0
for i in range 0 to n, do
   if str[i] = 0, then increase len
   else len := 0
   total := maximum of total and len
done
if total = n, then return n * k
prefix := length of maximal prefix with only 0
suffix:= length of maximal suffix with only 0
if k > 1, then
   total := max of total, and (prefix + suffix)
return total
End

उदाहरण

#include <iostream>
using namespace std;
int max_length_substring(string str, int n, int k) {
   int total_len = 0;
   int len = 0;
   for (int i = 0; i < n; ++i) {
      if (str[i] == '0') //if the current character is 0, increase len
         len++;
      else
         len = 0;
      total_len = max(total_len, len);
   }
   if (total_len == n) //if the whole string has 0 only
      return n * k;
   int prefix = 0, suffix = 0;
   for (int i = 0; str[i] == '0'; ++i, ++prefix) //find length of maximal prefix with only 0;
   for (int i = n - 1; str[i] == '0'; --i, ++suffix) //find length of maximal suffix with only 0;
   if (k > 1)
      total_len = max(total_len, prefix + suffix);
   return total_len;
}
int main() {
   int k = 3;
   string str = "0010010";
   int res = max_length_substring(str, str.length(), k);
   cout << "Maximum length of 0s: " << res;
}

आउटपुट

Maximum length of 0s: 3