Maximum Consecutive Zeroes in Concatenated Binary String
You are given a binary string str of length n. Suppose you create another string of size n * k by concatenating k copies of str together. What is the maximum size of a substring of the concatenated string consisting only of 0’s? Given that k > 1.
Examples:
Input : str = “110010”, k = 2
Output : 2
String becomes 110010110010 after two concatenations. This string has two zeroes.Input : str = “00100110”, k = 4
Output : 3
If the given string contains all zeroes then the answer is n * k. If S contains ones then the answer is either the maximum length of a substring of str containing only zeroes, or the sum between the length of the maximal prefix of S containing only zeroes and the length of the maximal suffix of str containing only zeroes. The last one must be computed only if k > 1.
Implementation:
C++
// C++ program to find maximum number // of consecutive zeroes after // concatenating a binary string #include<bits/stdc++.h> using namespace std; // returns the maximum size of a // substring consisting only of // zeroes after k concatenation int max_length_substring(string st, int n, int k) { // stores the maximum length // of the required substring int max_len = 0; int len = 0; for ( int i = 0; i < n; ++i) { // if the current character is 0 if (st[i] == '0' ) len++; else len = 0; // stores maximum length of current // substrings with zeroes max_len = max(max_len, len); } // if the whole string is // filled with zero if (max_len == n) return n * k; int pref = 0, suff = 0; // computes the length of the maximal // prefix which contains only zeroes for ( int i = 0; st[i] == '0' ; ++i, ++pref); // computes the length of the maximal // suffix which contains only zeroes for ( int i = n - 1; st[i] == '0' ; --i, ++suff); // if more than 1 concatenations // are to be made if (k > 1) max_len = max(max_len, pref + suff); return max_len; } // Driver code int main() { int n = 6; int k = 3; string st = "110010" ; int ans = max_length_substring(st, n, k); cout << ans; } // This code is contributed by ihritik |
Java
// Java program to find maximum number of // consecutive zeroes after concatenating // a binary string class GFG { // returns the maximum size of a substring // consisting only of zeroes // after k concatenation static int max_length_substring(String st, int n, int k) { // stores the maximum length of the // required substring int max_len = 0 ; int len = 0 ; for ( int i = 0 ; i < n; ++i) { // if the current character is 0 if (st.charAt(i) == '0' ) len++; else len = 0 ; // stores maximum length of current // substrings with zeroes max_len = Math.max(max_len, len); } // if the whole string is filled with zero if (max_len == n) return n * k; int pref = 0 , suff = 0 ; // computes the length of the maximal // prefix which contains only zeroes for ( int i = 0 ; st.charAt(i) == '0' ; ++i, ++pref) ; // computes the length of the maximal // suffix which contains only zeroes for ( int i = n - 1 ; st.charAt(i) == '0' ; --i, ++suff) ; // if more than 1 concatenations are to be made if (k > 1 ) max_len = Math.max(max_len, pref + suff); return max_len; } // Driver code public static void main(String[] args) { int n = 6 ; int k = 3 ; String st = "110010" ; int ans = max_length_substring(st, n, k); System.out.println(ans); } } |
Python3
# Python3 program to find maximum # number of consecutive zeroes # after concatenating a binary string # returns the maximum size of a # substring consisting only of # zeroes after k concatenation def max_length_substring(st, n, k): # stores the maximum length # of the required substring max_len = 0 len = 0 for i in range ( 0 , n): # if the current character is 0 if (st[i] = = '0' ): len = len + 1 ; else : len = 0 # stores maximum length of # current substrings with zeroes max_len = max (max_len, len ) # if the whole is filled # with zero if (max_len = = n): return n * k pref = 0 suff = 0 # computes the length of the maximal # prefix which contains only zeroes i = 0 while (st[i] = = '0' ): i = i + 1 pref = pref + 1 # computes the length of the maximal # suffix which contains only zeroes i = n - 1 while (st[i] = = '0' ): i = i - 1 suff = suff + 1 # if more than 1 concatenations # are to be made if (k > 1 ): max_len = max (max_len, pref + suff) return max_len # Driver code n = 6 k = 3 st = "110010" ans = max_length_substring(st, n, k) print (ans) # This code is contributed by ihritik |
C#
// C# program to find maximum number // of consecutive zeroes after // concatenating a binary string using System; class GFG { // returns the maximum size of // a substring consisting only // of zeroes after k concatenation static int max_length_substring( string st, int n, int k) { // stores the maximum length // of the required substring int max_len = 0; int len = 0; for ( int i = 0; i < n; ++i) { // if the current character is 0 if (st[i] == '0' ) len++; else len = 0; // stores maximum length of current // substrings with zeroes max_len = Math.Max(max_len, len); } // if the whole string is // filled with zero if (max_len == n) return n * k; int pref = 0, suff = 0; // computes the length of the maximal // prefix which contains only zeroes for ( int i = 0; st[i] == '0' ; ++i, ++pref); // computes the length of the maximal // suffix which contains only zeroes for ( int i = n - 1; st[i] == '0' ; --i, ++suff); // if more than 1 concatenations // are to be made if (k > 1) max_len = Math.Max(max_len, pref + suff); return max_len; } // Driver code public static void Main( string [] args) { int n = 6; int k = 3; string st = "110010" ; int ans = max_length_substring(st, n, k); Console.WriteLine(ans); } } // This code is contributed by ihritik |
PHP
<?php // PHP program to find maximum number // of consecutive zeroes after // concatenating a binary string // returns the maximum size of a // substring consisting only of // zeroes after k concatenation function max_length_substring( $st , $n , $k ) { // stores the maximum length // of the required substring $max_len = 0; $len = 0; for ( $i = 0; $i < $n ; ++ $i ) { // if the current character is 0 if ( $st [ $i ] == '0' ) $len ++; else $len = 0; // stores maximum length of // current substrings with zeroes $max_len = max( $max_len , $len ); } // if the whole $is filled // with zero if ( $max_len == $n ) return $n * $k ; $pref = 0; $suff = 0; // computes the length of the maximal // prefix which contains only zeroes for ( $i = 0; $st [ $i ] == '0' ; ++ $i , ++ $pref ); // computes the length of the maximal // suffix which contains only zeroes for ( $i = $n - 1; $st [ $i ] == '0' ; -- $i , ++ $suff ); // if more than 1 concatenations // are to be made if ( $k > 1) $max_len = max( $max_len , $pref + $suff ); return $max_len ; } // Driver code $n = 6; $k = 3; $st = "110010" ; $ans = max_length_substring( $st , $n , $k ); echo $ans ; // This code is contributed by ihritik ?> |
Javascript
//JavaScript program to find maximum // number of consecutive zeroes // after concatenating a binary string // returns the maximum size of a // substring consisting only of // zeroes after k concatenation function max_length_substring(st, n, k) { // stores the maximum length // of the required substring var max_len = 0; var len = 0; for ( var i = 0; i < n; i++) { // if the current character is 0 if (st[i] == '0' ) len = len + 1; else len = 0; // stores maximum length of // current substrings with zeroes max_len = Math.max(max_len, len); } // if the whole is filled // with zero if (max_len == n) return n * k; var pref = 0; var suff = 0; // computes the length of the maximal // prefix which contains only zeroes var i = 0; while (st[i] == '0' ) { i = i + 1; pref = pref + 1; } // computes the length of the maximal // suffix which contains only zeroes i = n - 1; while (st[i] == '0' ) { i = i - 1; suff = suff + 1; } // if more than 1 concatenations // are to be made if (k > 1) max_len = Math.max(max_len, pref + suff); return max_len; } // Driver code var n = 6; var k = 3; var st = "110010" ; //Function Call var ans = max_length_substring(st, n, k); console.log(ans); // This code is contributed by phasing17 |
2
Complexity Analysis:
- Time Complexity: O(N), where N represents the length of the given string.
- Auxiliary Space: O(1), no extra space is required, so it is a constant.
Contact Us