Given three integers N, P, and Q, the task is to count all possible distinct binary strings of length N such that each binary string does not contain P times consecutive 0’s and Q times consecutive 1’s.
Examples:
Input: N = 5, P = 2, Q = 3
Output: 7
Explanation: Binary strings that satisfy the given conditions are { “01010”, “01011”, “01101”, “10101”, “10110”, “11010”, “11011”}. Therefore, the required output is 7.Input: N = 5, P = 3, Q = 4
Output: 21
Naive Approach: The problem can be solved using Recursion. Following are the recurrence relations and their base cases :
At each possible index of a Binary String, either place the value ‘0‘ or place the value ‘1‘
Therefore, cntBinStr(str, N, P, Q) = cntBinStr(str + ‘0’, N, P, Q) + cntBinStr(str + ‘1’, N, P, Q)
where cntBinStr(str, N, P, Q) stores the count of distinct binary strings which does not contain P consecutive 1s and Q consecutive 0s.Base Case: If length(str) == N, check if str satisfy the given condition or not. If found to be true, return 1. Otherwise, return 0.
Below is the implementation of the above approach:
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 notbool 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 conditionint 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 Codeint 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.io.*;class GFG{ // Function to check if a// string satisfy the given// condition or notstatic 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 conditionstatic 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 Codepublic 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 notdef 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 # conditiondef 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 Codeif __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 notstatic 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 conditionstatic 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 Codepublic 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 notfunction 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 conditionfunction 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> |
Output
7
Time Complexity: O(2N)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach the idea is to use Dynamic Programming. Follow the steps below to solve the problem:
- Initialize two 2D arrays, say zero[N][P] and one[N][Q].
- zero[i][j] stores the count of binary strings of length i having j consecutive 0’s. Fill all the value of zero[i][j] in bottom-up manner.
Insert 0 at the ith index.
Case 1: If (i – 1)th index of string contains 1.
Case 2: If (i – 1)th index of string contains 0.
for all r in the range [2, P – 1].
![zero[i][1] = \sum\limits_{j=1}^{Q - 1}one[i - 1][j]](https://geeksforgeeks.org/wp-content/uploads/2023/10/dominic_rubhabha_quicklatex.com-b930e002b2bf7e3074b93baf352d56a6_l3.png "Rendered by QuickLaTeX.com")
![zero[i][j] = zero[i-1][j-1]](https://geeksforgeeks.org/wp-content/uploads/2023/10/dominic_rubhabha_quicklatex.com-5580cce2fc8299c7b32ac791bdec6513_l3.png "Rendered by QuickLaTeX.com")
- one[i][j] stores the count of binary strings of length i having j consecutive 1’s. Fill all the value of zero[i][j] in bottom-up manner.
Insert 1 at the ith index.
Case 1: If (i-1)th index of string contains 0.
Case 2: If (i-1)th index of string contains 1.
for all j in the range [2, Q – 1].
![one[i][1] = \sum\limits_{j=1}^{P - 1}zero[i - 1][j]](https://geeksforgeeks.org/wp-content/uploads/2023/10/wardslaus_quicklatex.com-8743c170976e6f94b86a81fc823b6d25_l3.png "Rendered by QuickLaTeX.com")
![one[i][j] = one[i-1][j-1]](https://geeksforgeeks.org/wp-content/uploads/2023/10/dominic_rubhabha_quicklatex.com-90e8c18555d0420a6de700c6fc2e8153_l3.png "Rendered by QuickLaTeX.com")
- Finally, print count of subarrays that satisfy the given condition.
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to count binary strings// that satisfy the given conditionint 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 Codeint main(){ int N = 5, P = 2, Q = 3; cout << cntBinStr(N, P, Q); return 0;} |
Java
// Java program to implement// the above approachimport java.io.*;class GFG{// Function to count binary Strings// that satisfy the given conditionstatic 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 Codepublic 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 conditiondef 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 Codeif __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 approachusing System;class GFG{// Function to count binary Strings// that satisfy the given conditionstatic 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 Codepublic 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 conditionfunction 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> |
Output
7
Time complexity: O(N * (P + Q))
Auxiliary Space: O(N * (P + Q))
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
