Contar posibles strings binarias de longitud N sin P 0s consecutivos y Q 1s consecutivos

Posted on by Rudeus Greyrat

Dados tres enteros N , P y Q , la tarea es contar todas las posibles strings binarias distintas de longitud N de modo que cada string binaria no contenga P veces 0 consecutivos y Q veces 1 consecutivos.

Ejemplos:

Entrada: N = 5, P = 2, Q = 3
Salida: 7
Explicación: Las strings binarias que cumplen las condiciones dadas son { «01010», «01011», «01101», «10101», «10110», «11010» , “11011”}. Por lo tanto, la salida requerida es 7.

Entrada: N = 5, P = 3, Q = 4
Salida: 21

 

Enfoque ingenuo: el problema se puede resolver utilizando Recursion . Las siguientes son las relaciones de recurrencia y sus casos base:

En cada índice posible de una string binaria, coloque el valor ‘ 0 ‘ o coloque el valor ‘ 1 ‘

Por lo tanto, cntBinStr(str, N, P, Q) = cntBinStr(str + ‘0’, N, P, Q) + cntBinStr(str + ‘1’, N, P, Q)
donde cntBinStr(str, N, P , Q) almacena el recuento de strings binarias distintas que no contienen P 1 s consecutivos y Q 0 s consecutivos .

Caso base: si length(str) == N , verifique si str satisface la condición dada o no. Si se encuentra que es cierto, devuelve 1. De lo contrario, devuelve 0.

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if a
// string satisfy the given
// condition or not
bool checkStr(string str,
              int P, int Q)
{
    // Stores the length
    // of string
    int N = str.size();
 
    // Stores the previous
    // character of the string
    char prev = str[0];
 
    // Stores the count of
    // consecutive equal characters
    int cnt = 0;
 
    // Traverse the string
    for (int i = 0; i < N;
         i++) {
 
        // If current character
        // is equal to the
        // previous character
        if (str[i] == prev) {
 
            cnt++;
        }
        else {
 
            // If count of consecutive
            // 1s is more than Q
            if (prev == '1' && cnt >= Q) {
 
                return false;
            }
 
            // If count of consecutive
            // 0s is more than P
            if (prev == '0' && cnt >= P) {
 
                return false;
            }
 
            // Reset value of cnt
            cnt = 1;
        }
 
        prev = str[i];
    }
 
    // If count of consecutive
    // 1s is more than Q
    if (prev == '1' && cnt >= Q) {
        return false;
    }
 
    // If count of consecutive
    // 0s is more than P
    if (prev == '0' && cnt >= P) {
        return false;
    }
 
    return true;
}
 
// Function to count all distinct
// binary strings that satisfy
// the given condition
int cntBinStr(string str, int N,
              int P, int Q)
{
    // Stores the length of str
    int len = str.size();
 
    // If length of str is N
    if (len == N) {
 
        // If str satisfy
        // the given condition
        if (checkStr(str, P, Q))
            return 1;
 
        // If str does not satisfy
        // the given condition
        return 0;
    }
 
    // Append a character '0' at
    // end of str
    int X = cntBinStr(str + '0',
                      N, P, Q);
 
    // Append a character '1' at
    // end of str
    int Y = cntBinStr(str + '1',
                      N, P, Q);
 
    // Return total count
    // of binary strings
    return X + Y;
}
 
// Driver Code
int main()
{
    int N = 5, P = 2, Q = 3;
    cout << cntBinStr("", N, P, Q);
 
    return 0;
}

Java

// Java program to implement
// the above approach 
class GFG{
   
// Function to check if a
// string satisfy the given
// condition or not
static boolean checkStr(String str,
                        int P, int Q)
{
     
    // Stores the length
    // of string
    int N = str.length();
   
    // Stores the previous
    // character of the string
    char prev = str.charAt(0);
   
    // Stores the count of
    // consecutive equal characters
    int cnt = 0;
   
    // Traverse the string
    for(int i = 0; i < N; i++)
    {
          
        // If current character
        // is equal to the
        // previous character
        if (str.charAt(i) == prev)
        {
            cnt++;
        }
        else
        {
              
            // If count of consecutive
            // 1s is more than Q
            if (prev == '1' && cnt >= Q)
            {
                return false;
            }
   
            // If count of consecutive
            // 0s is more than P
            if (prev == '0' && cnt >= P)
            {
                return false;
            }
   
            // Reset value of cnt
            cnt = 1;
        }
        prev = str.charAt(i);
    }
   
    // If count of consecutive
    // 1s is more than Q
    if (prev == '1' && cnt >= Q)
    {
        return false;
    }
   
    // If count of consecutive
    // 0s is more than P
    if (prev == '0' && cnt >= P)
    {
        return false;
    }
    return true;
}
   
// Function to count all distinct
// binary strings that satisfy
// the given condition
static int cntBinStr(String str, int N,
                          int P, int Q)
{
     
    // Stores the length of str
    int len = str.length();
   
    // If length of str is N
    if (len == N)
    {
          
        // If str satisfy
        // the given condition
        if (checkStr(str, P, Q))
            return 1;
   
        // If str does not satisfy
        // the given condition
        return 0;
    }
   
    // Append a character '0' at
    // end of str
    int X = cntBinStr(str + '0',
                      N, P, Q);
   
    // Append a character '1' at
    // end of str
    int Y = cntBinStr(str + '1',
                      N, P, Q);
   
    // Return total count
    // of binary strings
    return X + Y;
}
   
// Driver Code
public static void main (String[] args)
{
    int N = 5, P = 2, Q = 3;
      
    System.out.println(cntBinStr("", N, P, Q));
}
}
 
// This code is contributed by code_hunt

Python3

# Python3 program to implement
# the above approach
 
# Function to check if a
# satisfy the given
# condition or not
def checkStr(str, P, Q):
     
    # Stores the length
    # of string
    N = len(str)
 
    # Stores the previous
    # character of the string
    prev = str[0]
 
    # Stores the count of
    # consecutive equal
    # characters
    cnt = 0
 
    # Traverse the string
    for i in range(N):
         
        # If current character
        # is equal to the
        # previous character
        if (str[i] == prev):
            cnt += 1
 
        else:
             
            # If count of consecutive
            # 1s is more than Q
            if (prev == '1' and
                cnt >= Q):
                return False
 
            # If count of consecutive
            # 0s is more than P
            if (prev == '0' and
                cnt >= P):
                return False
 
            # Reset value of cnt
            cnt = 1
 
        prev = str[i]
 
    # If count of consecutive
    # 1s is more than Q
    if (prev == '1'and
        cnt >= Q):
        return False
 
    # If count of consecutive
    # 0s is more than P
    if (prev == '0' and
        cnt >= P):
        return False
 
    return True
 
# Function to count all
# distinct binary strings
# that satisfy the given
# condition
def cntBinStr(str, N,
              P, Q):
     
    # Stores the length
    # of str
    lenn = len(str)
 
    # If length of str
    # is N
    if (lenn == N):
 
        # If str satisfy
        # the given condition
        if (checkStr(str, P, Q)):
            return 1
 
        # If str does not satisfy
        # the given condition
        return 0
 
    # Append a character '0'
    # at end of str
    X = cntBinStr(str + '0',
                  N, P, Q)
 
    # Append a character
    # '1' at end of str
    Y = cntBinStr(str + '1',
                  N, P, Q)
 
    # Return total count
    # of binary strings
    return X + Y
 
# Driver Code
if __name__ == '__main__':
     
    N = 5
    P = 2
    Q = 3   
    print(cntBinStr("", N,
                    P, Q))
 
# This code is contributed by mohit kumar 29

C#

// C# program to implement
// the above approach 
using System;
 
class GFG{
  
// Function to check if a
// string satisfy the given
// condition or not
static bool checkStr(string str,
                     int P, int Q)
{
     
    // Stores the length
    // of string
    int N = str.Length;
  
    // Stores the previous
    // character of the string
    char prev = str[0];
  
    // Stores the count of
    // consecutive equal characters
    int cnt = 0;
  
    // Traverse the string
    for(int i = 0; i < N; i++)
    {
         
        // If current character
        // is equal to the
        // previous character
        if (str[i] == prev)
        {
            cnt++;
        }
        else
        {
             
            // If count of consecutive
            // 1s is more than Q
            if (prev == '1' && cnt >= Q)
            {
                return false;
            }
  
            // If count of consecutive
            // 0s is more than P
            if (prev == '0' && cnt >= P)
            {
                return false;
            }
  
            // Reset value of cnt
            cnt = 1;
        }
  
        prev = str[i];
    }
  
    // If count of consecutive
    // 1s is more than Q
    if (prev == '1' && cnt >= Q)
    {
        return false;
    }
  
    // If count of consecutive
    // 0s is more than P
    if (prev == '0' && cnt >= P)
    {
        return false;
    }
     
    return true;
}
  
// Function to count all distinct
// binary strings that satisfy
// the given condition
static int cntBinStr(string str, int N,
                          int P, int Q)
{
     
    // Stores the length of str
    int len = str.Length;
  
    // If length of str is N
    if (len == N)
    {
         
        // If str satisfy
        // the given condition
        if (checkStr(str, P, Q))
            return 1;
  
        // If str does not satisfy
        // the given condition
        return 0;
    }
  
    // Append a character '0' at
    // end of str
    int X = cntBinStr(str + '0',
                      N, P, Q);
  
    // Append a character '1' at
    // end of str
    int Y = cntBinStr(str + '1',
                      N, P, Q);
  
    // Return total count
    // of binary strings
    return X + Y;
}
  
// Driver Code
public static void Main ()
{
    int N = 5, P = 2, Q = 3;
     
    Console.WriteLine(cntBinStr("", N, P, Q));
}
}
 
// This code is contributed by sanjoy_62

Javascript

<script>
 
// Javascript program to implement
// the above approach
 
// Function to check if a
// string satisfy the given
// condition or not
function checkStr(str, P, Q)
{
     
    // Stores the length
    // of string
    let N = str.length;
   
    // Stores the previous
    // character of the string
    let prev = str[0];
   
    // Stores the count of
    // consecutive equal characters
    let cnt = 0;
   
    // Traverse the string
    for(let i = 0; i < N; i++)
    {
          
        // If current character
        // is equal to the
        // previous character
        if (str[i] == prev)
        {
            cnt++;
        }
        else
        {
              
            // If count of consecutive
            // 1s is more than Q
            if (prev == '1' && cnt >= Q)
            {
                return false;
            }
   
            // If count of consecutive
            // 0s is more than P
            if (prev == '0' && cnt >= P)
            {
                return false;
            }
   
            // Reset value of cnt
            cnt = 1;
        }
        prev = str[i];
    }
   
    // If count of consecutive
    // 1s is more than Q
    if (prev == '1' && cnt >= Q)
    {
        return false;
    }
   
    // If count of consecutive
    // 0s is more than P
    if (prev == '0' && cnt >= P)
    {
        return false;
    }
    return true;
}
   
// Function to count all distinct
// binary strings that satisfy
// the given condition
function cntBinStr(str, N, P, Q)
{
     
    // Stores the length of str
    let len = str.length;
   
    // If length of str is N
    if (len == N)
    {
          
        // If str satisfy
        // the given condition
        if (checkStr(str, P, Q))
            return 1;
   
        // If str does not satisfy
        // the given condition
        return 0;
    }
   
    // Append a character '0' at
    // end of str
    let X = cntBinStr(str + '0',
                      N, P, Q);
   
    // Append a character '1' at
    // end of str
    let Y = cntBinStr(str + '1',
                      N, P, Q);
   
    // Return total count
    // of binary strings
    return X + Y;
}
 
// Driver Code
 
    let N = 5, P = 2, Q = 3;
      
    document.write(cntBinStr("", N, P, Q));
     
</script>
Producción

7

Complejidad temporal: O(2 N )
Espacio auxiliar: O(1)

Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar la programación dinámica . Siga los pasos a continuación para resolver el problema:

  • Inicialice dos arrays 2D , digamos zero[N][P] y one[N][Q] .
  • zero[i][j] almacena el recuento de strings binarias de longitud i que tienen j 0 consecutivos. Rellene todo el valor de cero[i][j] de forma ascendente.

Inserte 0 en el i -ésimo índice. 
Caso 1: Si (i – 1) el índice de la string contiene 1. 
 

cero[i][1] = \sum\limits_{j=1}^{Q - 1}uno[i - 1][j]
 

Caso 2: Si (i – 1) el índice de la string contiene 0.

cero[i][j] = cero[i-1][j-1]
 

para todo r en el rango [2, P – 1]. 

 

  • one[i][j] almacena el recuento de strings binarias de longitud i que tienen j 1 consecutivos. Rellene todo el valor de cero[i][j] de forma ascendente.

Inserte 1 en el i -ésimo índice. 
Caso 1: Si (i-1) el índice de la string contiene 0. 
 

uno[i][1] = \sum\limits_{j=1}^{P - 1}cero[i - 1][j]
 

Caso 2: Si (i-1) el índice de la string contiene 1.

uno[i][j] = uno[i-1][j-1]
 

para todo j en el rango [2, Q – 1]. 

 

  • Finalmente, imprime el conteo de subarreglos que satisfacen la condición dada.

C++

// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count binary strings
// that satisfy the given condition
int cntBinStr(int N, int P, int Q)
{
    // zero[i][j] stores count
    // of binary strings of length i
    // having j consecutive 0s
    int zero[N + 1][P];
 
    // one[i][j] stores count
    // of binary strings of length i
    // having j consecutive 1s
    int one[N + 1][Q];
 
    // Set all values of
    // zero[][] array to 0
    memset(zero, 0, sizeof(zero));
 
    // Set all values of
    // one[i][j] array to 0
    memset(one, 0, sizeof(one));
 
    // Base case
    zero[1][1] = one[1][1] = 1;
 
    // Fill all the values of zero[i][j]
    // and one[i][j] in bottom up manner
    for (int i = 2; i <= N; i++) {
 
        for (int j = 2; j < P;
             j++) {
            zero[i][j] = zero[i - 1][j - 1];
        }
 
        for (int j = 1; j < Q;
             j++) {
            zero[i][1] = zero[i][1] + one[i - 1][j];
        }
 
        for (int j = 2; j < Q;
             j++) {
            one[i][j] = one[i - 1][j - 1];
        }
 
        for (int j = 1; j < P;
             j++) {
            one[i][1] = one[i][1] + zero[i - 1][j];
        }
    }
 
    // Stores count of binary strings
    // that satisfy the given condition
    int res = 0;
 
    // Count binary strings of
    // length N having less than
    // P consecutive 0s
    for (int i = 1; i < P; i++) {
        res = res + zero[N][i];
    }
 
    // Count binary strings of
    // length N having less than
    // Q consecutive 1s
    for (int i = 1; i < Q; i++) {
        res = res + one[N][i];
    }
 
    return res;
}
 
// Driver Code
int main()
{
    int N = 5, P = 2, Q = 3;
    cout << cntBinStr(N, P, Q);
    return 0;
}

Java

// Java program to implement
// the above approach
import java.util.*;
 
class GFG{
 
// Function to count binary Strings
// that satisfy the given condition
static int cntBinStr(int N, int P, int Q)
{
     
    // zero[i][j] stores count
    // of binary Strings of length i
    // having j consecutive 0s
    int [][]zero = new int[N + 1][P];
 
    // one[i][j] stores count
    // of binary Strings of length i
    // having j consecutive 1s
    int [][]one = new int[N + 1][Q];
 
    // Base case
    zero[1][1] = one[1][1] = 1;
 
    // Fill all the values of zero[i][j]
    // and one[i][j] in bottom up manner
    for(int i = 2; i <= N; i++)
    {
        for(int j = 2; j < P; j++)
        {
            zero[i][j] = zero[i - 1][j - 1];
        }
 
        for(int j = 1; j < Q; j++)
        {
            zero[i][1] = zero[i][1] +
                          one[i - 1][j];
        }
 
        for(int j = 2; j < Q; j++)
        {
            one[i][j] = one[i - 1][j - 1];
        }
 
        for(int j = 1; j < P; j++)
        {
            one[i][1] = one[i][1] +
                       zero[i - 1][j];
        }
    }
 
    // Stores count of binary Strings
    // that satisfy the given condition
    int res = 0;
 
    // Count binary Strings of
    // length N having less than
    // P consecutive 0s
    for(int i = 1; i < P; i++)
    {
        res = res + zero[N][i];
    }
 
    // Count binary Strings of
    // length N having less than
    // Q consecutive 1s
    for(int i = 1; i < Q; i++)
    {
        res = res + one[N][i];
    }
    return res;
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 5, P = 2, Q = 3;
     
    System.out.print(cntBinStr(N, P, Q));
}
}
 
// This code is contributed by Amit Katiyar

Python3

# Python3 program to implement
# the above approach
 
# Function to count binary
# Strings that satisfy the
# given condition
def cntBinStr(N, P, Q):
   
    # zero[i][j] stores count
    # of binary Strings of length i
    # having j consecutive 0s
    zero = [[0 for i in range(P)]
               for j in range(N + 1)];
 
    # one[i][j] stores count
    # of binary Strings of length i
    # having j consecutive 1s
    one = [[0 for i in range(Q)]
              for j in range(N + 1)];
 
    # Base case
    zero[1][1] = one[1][1] = 1;
 
    # Fill all the values of
    # zero[i][j] and one[i][j]
    # in bottom up manner
    for i in range(2, N + 1):
        for j in range(2, P):
            zero[i][j] = zero[i - 1][j - 1];
 
        for j in range(1, Q):
            zero[i][1] = (zero[i][1] +
                          one[i - 1][j]);
 
        for j in range(2, Q):
            one[i][j] = one[i - 1][j - 1];
 
        for j in range(1, P):
            one[i][1] = one[i][1] + zero[i - 1][j];
 
    # Stores count of binary
    # Strings that satisfy
    # the given condition
    res = 0;
 
    # Count binary Strings of
    # length N having less than
    # P consecutive 0s
    for i in range(1, P):
        res = res + zero[N][i];
 
    # Count binary Strings of
    # length N having less than
    # Q consecutive 1s
    for i in range(1, Q):
        res = res + one[N][i];
 
    return res;
 
# Driver Code
if __name__ == '__main__':
   
    N = 5;
    P = 2;
    Q = 3;
    print(cntBinStr(N, P, Q));
 
# This code is contributed by gauravrajput1

C#

// C# program to implement
// the above approach
using System;
 
class GFG{
 
// Function to count binary Strings
// that satisfy the given condition
static int cntBinStr(int N, int P, int Q)
{
     
    // zero[i,j] stores count
    // of binary Strings of length i
    // having j consecutive 0s
    int [,]zero = new int[N + 1, P];
 
    // one[i,j] stores count
    // of binary Strings of length i
    // having j consecutive 1s
    int [,]one = new int[N + 1, Q];
 
    // Base case
    zero[1, 1] = one[1, 1] = 1;
 
    // Fill all the values of zero[i,j]
    // and one[i,j] in bottom up manner
    for(int i = 2; i <= N; i++)
    {
        for(int j = 2; j < P; j++)
        {
            zero[i, j] = zero[i - 1, j - 1];
        }
 
        for(int j = 1; j < Q; j++)
        {
            zero[i, 1] = zero[i, 1] +
                          one[i - 1, j];
        }
 
        for(int j = 2; j < Q; j++)
        {
            one[i, j] = one[i - 1, j - 1];
        }
 
        for(int j = 1; j < P; j++)
        {
            one[i, 1] = one[i, 1] +
                       zero[i - 1, j];
        }
    }
 
    // Stores count of binary Strings
    // that satisfy the given condition
    int res = 0;
 
    // Count binary Strings of
    // length N having less than
    // P consecutive 0s
    for(int i = 1; i < P; i++)
    {
        res = res + zero[N, i];
    }
 
    // Count binary Strings of
    // length N having less than
    // Q consecutive 1s
    for(int i = 1; i < Q; i++)
    {
        res = res + one[N, i];
    }
    return res;
}
 
// Driver Code
public static void Main(String[] args)
{
    int N = 5, P = 2, Q = 3;
     
    Console.Write(cntBinStr(N, P, Q));
}
}
 
// This code is contributed by gauravrajput1

Javascript

<script>
 
// JavaScript program to implement
// the above approach
 
// Function to count binary strings
// that satisfy the given condition
function cntBinStr(N, P, Q)
{
    // zero[i][j] stores count
    // of binary strings of length i
    // having j consecutive 0s
    //and
    // Set all values of
    // zero[][] array to 0
    var zero = new Array(N+1).fill(0).
    map(item=>(new Array(P).fill(0)));
     
    // one[i][j] stores count
    // of binary strings of length i
    // having j consecutive 1s
    //and
    // Set all values of
    // one[i][j] array to 0
    var one  = new Array(N+1).fill(0).
    map(item=>(new Array(Q).fill(0)));;
    
    // Base case
    zero[1][1] = one[1][1] = 1;
 
    // Fill all the values of zero[i][j]
    // and one[i][j] in bottom up manner
    for (var i = 2; i <= N; i++) {
 
        for (var j = 2; j < P;
             j++) {
            zero[i][j] = zero[i - 1][j - 1];
        }
 
        for (var j = 1; j < Q;
             j++) {
            zero[i][1] = zero[i][1] + one[i - 1][j];
        }
 
        for (var j = 2; j < Q;
             j++) {
            one[i][j] = one[i - 1][j - 1];
        }
 
        for (var j = 1; j < P;
             j++) {
            one[i][1] = one[i][1] + zero[i - 1][j];
        }
    }
 
    // Stores count of binary strings
    // that satisfy the given condition
    var res = 0;
 
    // Count binary strings of
    // length N having less than
    // P consecutive 0s
    for (var i = 1; i < P; i++) {
        res = res + zero[N][i];
    }
 
    // Count binary strings of
    // length N having less than
    // Q consecutive 1s
    for (var i = 1; i < Q; i++) {
        res = res + one[N][i];
    }
 
    return res;
}
 
var N = 5, P = 2, Q = 3;
 document.write( cntBinStr(N, P, Q));
 
// This code in contributed by SoumikMondal
 
</script>
Producción

7

Complejidad temporal: O(N * (P + Q))
Espacio auxiliar: O(N * (P + Q))

Publicación traducida automáticamente

Artículo escrito por lostsoul27 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *