Maximum Consecutive Zeroes in Concatenated Binary String

Last Updated : 07 Sep, 2022

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# 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

Output

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.