Given an integer N, the task is to count the number of binary strings possible of length N such that they don’t contain “111” as a substring. The answer could be large so print answer modulo 109 + 7.
Examples:
Input: N = 3
Output: 7
All possible substring are “000”, “001”,
“010”, “011”, “100”, “101” and “110”.
“111” is not a valid string.
Input N = 16
Output: 19513
Approach: Dynamic programming can be used to solve this problem. Create a dp[][] array where dp[i][j] will store the count of possible substrings such that 1 appears j times consecutively upto the ith index. Now, the recurrence relations will be:
dp[i][0] = dp[i – 1][0] + dp[i – 1][1] + dp[i – 1][2]
dp[i][1] = dp[i – 1][0]
dp[i][2] = dp[i – 1][1]
And the base cases will be dp[1][0] = 1, dp[1][1] = 1 and dp[1][2] = 0. Now, the required count of strings will be dp[N][0] + dp[N][1] + dp[N][2].
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;const long MOD = 1000000007;// Function to return the count// of all possible valid stringslong countStrings(long N){ long dp[N + 1][3]; // Fill 0's in the dp array memset(dp, 0, sizeof(dp)); // Base cases dp[1][0] = 1; dp[1][1] = 1; dp[1][2] = 0; for (int i = 2; i <= N; i++) { // dp[i][j] = number of possible strings // such that '1' just appeared consecutively // j times upto the ith index dp[i][0] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % MOD; // Taking previously calculated value dp[i][1] = dp[i - 1][0] % MOD; dp[i][2] = dp[i - 1][1] % MOD; } // Taking all possible cases that // can appear at the Nth position long ans = (dp[N][0] + dp[N][1] + dp[N][2]) % MOD; return ans;}// Driver codeint main(){ long N = 3; cout << countStrings(N); return 0;} |
Java
// Java implementation of the approach class GFG { final static int MOD = 1000000007; // Function to return the count // of all possible valid strings static long countStrings(int N) { int i, j; int dp[][] = new int[N + 1][3]; // Fill 0's in the dp array for(i = 0; i < N + 1; i++) { for(j = 9; j < 3 ; j ++) { dp[i][j] = 0; } } // Base cases dp[1][0] = 1; dp[1][1] = 1; dp[1][2] = 0; for (i = 2; i <= N; i++) { // dp[i][j] = number of possible strings // such that '1' just appeared consecutively // j times upto the ith index dp[i][0] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % MOD; // Taking previously calculated value dp[i][1] = dp[i - 1][0] % MOD; dp[i][2] = dp[i - 1][1] % MOD; } // Taking all possible cases that // can appear at the Nth position int ans = (dp[N][0] + dp[N][1] + dp[N][2]) % MOD; return ans; } // Driver code public static void main (String[] args) { int N = 3; System.out.println(countStrings(N)); } }// This code is contributed by AnkitRai01 |
Python3
# Python3 implementation of the approach MOD = 1000000007# Function to return the count # of all possible valid strings def countStrings(N): # Initialise and fill 0's in the dp array dp = [[0] * 3 for i in range(N + 1)] # Base cases dp[1][0] = 1; dp[1][1] = 1; dp[1][2] = 0; for i in range(2, N + 1): # dp[i][j] = number of possible strings # such that '1' just appeared consecutively # j times upto the ith index dp[i][0] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % MOD # Taking previously calculated value dp[i][1] = dp[i - 1][0] % MOD dp[i][2] = dp[i - 1][1] % MOD # Taking all possible cases that # can appear at the Nth position ans = (dp[N][0] + dp[N][1] + dp[N][2]) % MOD return ans # Driver codeif __name__ == '__main__': N = 3 print(countStrings(N)) # This code is contributed by ashutosh450 |
C#
// C# implementation of the above approach using System; class GFG { static readonly int MOD = 1000000007; // Function to return the count // of all possible valid strings static long countStrings(int N) { int i, j; int [,]dp = new int[N + 1, 3]; // Fill 0's in the dp array for(i = 0; i < N + 1; i++) { for(j = 9; j < 3; j ++) { dp[i, j] = 0; } } // Base cases dp[1, 0] = 1; dp[1, 1] = 1; dp[1, 2] = 0; for (i = 2; i <= N; i++) { // dp[i,j] = number of possible strings // such that '1' just appeared consecutively // j times upto the ith index dp[i, 0] = (dp[i - 1, 0] + dp[i - 1, 1] + dp[i - 1, 2]) % MOD; // Taking previously calculated value dp[i, 1] = dp[i - 1, 0] % MOD; dp[i, 2] = dp[i - 1, 1] % MOD; } // Taking all possible cases that // can appear at the Nth position int ans = (dp[N, 0] + dp[N, 1] + dp[N, 2]) % MOD; return ans; } // Driver code public static void Main (String[] args) { int N = 3; Console.WriteLine(countStrings(N)); } }// This code is contributed by Rajput-Ji |
Javascript
<script>// javascript implementation of the approach var MOD = 1000000007; // Function to return the count // of all possible valid strings function countStrings(N) { var i, j; var dp = Array(N+1).fill(0).map(x => Array(3).fill(0)); // Fill 0's in the dp array for(i = 0; i < N + 1; i++) { for(j = 9; j < 3 ; j ++) { dp[i][j] = 0; } } // Base cases dp[1][0] = 1; dp[1][1] = 1; dp[1][2] = 0; for (i = 2; i <= N; i++) { // dp[i][j] = number of possible strings // such that '1' just appeared consecutively // j times upto the ith index dp[i][0] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % MOD; // Taking previously calculated value dp[i][1] = dp[i - 1][0] % MOD; dp[i][2] = dp[i - 1][1] % MOD; } // Taking all possible cases that // can appear at the Nth position var ans = (dp[N][0] + dp[N][1] + dp[N][2]) % MOD; return ans; } // Driver code var N = 3; document.write(countStrings(N)); // This code is contributed by 29AjayKumar </script> |
Output:
7
Time Complexity: O(N)
Auxiliary Space: O(N)
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!
