ধরুন আমাদের দৈর্ঘ্যের একটি বাইনারি স্ট্রিং আছে, আরেকটি মান বলুন k দেওয়া আছে। আমাদের বাইনারি স্ট্রিং কে বার সংযুক্ত করতে হবে। তারপর আমাদের সংযুক্ত স্ট্রিং-এ পরপর 0s-এর সর্বাধিক সংখ্যা খুঁজে বের করতে হবে। ধরুন বাইনারি স্ট্রিং হল “0010010”, এবং k =2, তারপর স্ট্রিং k বার সংযুক্ত করার পরে, এটি হবে “00100100010010”। তাই পরপর 0 এর সর্বোচ্চ সংখ্যা হল 3।
পদ্ধতি সহজ. যদি সংখ্যাটির সবগুলো 0 থাকে, তাহলে উত্তর হবে n * k। যদি স্ট্রিংটিতে একটি থাকে, তাহলে ফলাফলটি হয় স্ট্রিং এর একটি সাবস্ট্রিং এর সর্বাধিক দৈর্ঘ্য হবে, যার মধ্যে সমস্ত 0s রয়েছে, অথবা শুধুমাত্র 0s ধারণকারী স্ট্রিংটির সর্বাধিক উপসর্গের দৈর্ঘ্য এবং এর সর্বাধিক প্রত্যয়ের দৈর্ঘ্যের মধ্যে যোগফল হবে একটি স্ট্রিং যেখানে শুধুমাত্র 0s আছে।
অ্যালগরিদম
সর্বোচ্চ_শূন্য_গণনা (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
