मान लीजिए हमारे पास लंबाई n की एक बाइनरी स्ट्रिंग है, एक अन्य मान k दिया गया है। हमें बाइनरी स्ट्रिंग को k बार संयोजित करना है। फिर हमें संयोजित स्ट्रिंग में अधिकतम लगातार 0 की संख्या ढूंढनी है। मान लीजिए बाइनरी स्ट्रिंग "0010010" है, और k = 2, तो k बार स्ट्रिंग संयोजित करने के बाद, यह "00100100010010" हो जाएगी। तो अधिकतम लगातार 0 की संख्या 3 है।
दृष्टिकोण सरल है। यदि संख्या में सभी 0 हैं, तो उत्तर n * k होगा। यदि स्ट्रिंग में 1 हैं, तो परिणाम या तो स्ट्रिंग के केवल 0 वाले सबस्ट्रिंग की अधिकतम लंबाई होगी, या केवल 0 वाले स्ट्रिंग के अधिकतम प्रीफिक्स की लंबाई और केवल 0 वाले स्ट्रिंग के अधिकतम सफिक्स की लंबाई का योग होगी।
एल्गोरिदम
max_zero_count (str, n, k) −
शुरुआत total := 0 len := 0 i को 0 से n तक की रेंज के लिए करें यदि str[i] = 0, तो len बढ़ाएं अन्यथा len := 0 total := total और len का अधिकतम किया गया यदि total = n, तो n * k वापस करें prefix := केवल 0 वाले अधिकतम प्रीफिक्स की लंबाई suffix:= केवल 0 वाले अधिकतम सफिक्स की लंबाई यदि k > 1, तो total := total और (prefix + suffix) का अधिकतम total वापस करें समाप्त
उदाहरण
#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') //यदि वर्तमान कैरेक्टर 0 है, तो len बढ़ाएं len++; else len = 0; total_len = max(total_len, len); } if (total_len == n) //यदि पूरी स्ट्रिंग में केवल 0 हैं return n * k; int prefix = 0, suffix = 0; for (int i = 0; str[i] == '0'; ++i, ++prefix) //केवल 0 वाले अधिकतम प्रीफिक्स की लंबाई ढूंढें; for (int i = n - 1; str[i] == '0'; --i, ++suffix) //केवल 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 << "0 की अधिकतम लंबाई: " << res; } आउटपुट
0 की अधिकतम लंबाई: 3
