ধরুন দৈর্ঘ্য n-এর একটি বাইনারি স্ট্রিং আছে, আরেকটি মান k দেওয়া আছে। বাইনারি স্ট্রিংটি k বার কনক্যাটেনেট করতে হবে। তারপর কনক্যাটেনেটেড স্ট্রিং-এ সর্বোচ্চ কতটি সান্তানিক ০ আছে তা বের করতে হবে। ধরুন বাইনারি স্ট্রিংটি "0010010", এবং k = 2, তবে k বার কনক্যাটেনেট করলে হবে "00100100010010"। তাহলে সর্বোচ্চ সান্তানিক ০-এর সংখ্যা ৩।
পদ্ধতিটি সহজ। যদি স্ট্রিংটি সম্পূর্ণ ০ হয়, তবে উত্তর হবে n * k। যদি স্ট্রিং-এ ১ থাকে, তবে ফলাফল হবে είτε স্ট্রিং-এ সবচেয়ে বড় শুধু ০ সম্বলিত সাবস্ট্রিং-এর দৈর্ঘ্য, অথবা শুধু ০ সম্বলিত সর্বোচ্চ প্রিফিক্সের দৈর্ঘ্য এবং শুধু ০ সম্বলিত সর্বোচ্চ সাফিক্সের দৈর্ঘ্যের যোগফল।
আলগরিদম
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
C++ প্রোগ্রাম উদাহরণ
#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') // যদি বর্তমান ক্যারেক্টার ০ হয়, len বাড়ান
len++;
else
len = 0;
total_len = max(total_len, len);
}
if (total_len == n) // যদি পুরো স্ট্রিং শুধু ০ হয়
return n * k;
int prefix = 0, suffix = 0;
for (int i = 0; str[i] == '0'; ++i, ++prefix) // শুধু ০ সম্বলিত সর্বোচ্চ প্রিফিক্সের দৈর্ঘ্য
;
for (int i = n - 1; str[i] == '0'; --i, ++suffix) // শুধু ০ সম্বলিত সর্বোচ্চ সাফিক্সের দৈর্ঘ্য
;
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;
return 0;
}
আউটপুট
Maximum length of 0s: 3
