# 计算可能的长度为N的二进制字符串，而没有P个连续的0和Q个连续的1

2021年5月1日17:20:44 发表评论 795 次浏览

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

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

//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 lenngth
# 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 lenngth 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)

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

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

``7``

O(2

N

)

O(1)

• 初始化两个2D 数组说零[N] [P]和一个[N] [Q].
• 零[i] [j]存储长度为二​​进制的字符串的计数一世有Ĵ连续0。填满所有的值零[i] [j]以自下而上的方式。

• 一个[i] [j]存储长度为二​​进制的字符串的计数一世有Ĵ连续1个。以自下而上的方式填充所有零[i] [j]的值。

• 最后, 打印满足给定条件的子数组的计数。

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

``7``