Máximo de ceros consecutivos en strings binarias concatenadas

Se le da una string binaria str de longitud n . Suponga que crea otra string de tamaño n * k concatenando k copias de str juntas. ¿Cuál es el tamaño máximo de una substring de la string concatenada que consta solo de 0? Dado que k > 1. Ejemplos:

Entrada: str = “110010”, k = 2 Salida: 2 String se convierte en 110010110010 después de dos concatenaciones. Esta string tiene dos ceros. Entrada: str = “00100110”, k = 4 Salida: 3

Si la string dada contiene solo ceros, la respuesta es n * k. Si S contiene unos, la respuesta es la longitud máxima de una substring de str que contiene solo ceros, o la suma entre la longitud del prefijo máximo de S que contiene solo ceros y la longitud del sufijo máximo de str que contiene solo ceros. El último debe calcularse solo si k > 1. 

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

Complejidad de tiempo: O(N), donde N representa la longitud de la string dada.
Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.