Given an integer n(1 <= n <= 105), the task is to count valid string S of length n, which contains characters ‘0’, ‘1’, or ‘2’ only. For a valid string, it must follow the below conditions.
- There should not be more than K1 occurrences of ‘0’.
- There should not be more than K2 consecutive ‘1’s. (1 <= K1, K2 <= 10)
Note: The answer may be very large, so return it modulo 109 + 7.
Examples:
Input: n = 2, K1 = 1, K2 = 2
Output: 8
Explanation: There are 8 valid strings of length 2: “22”, “02”, “20”, “12”, “21”, “01”, “10”, “11”. “00” is not valid string because there should not be more than one occurrence of ‘0’.Input: n = 5, K1 = 2, K2 = 3;
Output: 139Input: n = n = 1012, K1 = 3, K2 = 5
Output: 663818944
Counting valid strings that contain ‘0’, ‘1’, or ‘2’ using Recursion:
- Base Case: When n becomes 0, this indicates that a valid string of the desired length has been generated. So, return 1.
- Within the countValidString() function, iterates over the three possible characters: ‘0’, ‘1’, and ‘2’. For each character, checks if it can be added to the string based on the constraints:
- If zeroCount < K1, we can add ‘0’ to the string. So, recur for rest of the length and store result in res1.
- If oneCount < K2, we can add ‘1’ to the string. So, recur for rest of the length and store result in res2.
- We can always add ‘2’ to the string. So, recur for rest of the length and store result in res3.
- Finally, return the overall result = (res1 + res2 + res3) % 1e9+7.
Below is the implementation of the above approach:
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;// Define a modulo valueint mod = 1e9 + 7;// Recursive function to calculate the number// of valid stringsint countValidString(int zeroCount, int oneCount, int K1, int K2, int n){ // Base case: If n becomes 0, return 1 // as a valid record is found if (n == 0) return 1; // Initialize variables to store // different results long long res1 = 0, res2 = 0, res3 = 0; // Iterate over three possible // characters: 0, 1, and 2 for (int i = 0; i <= 2; i++) { // Check if we can add '0' to // the string (zeroCount < K1) if (zeroCount < K1 && i == 0) { res1 = countValidString(zeroCount + 1, 0, K1, K2, n - 1); } // Check if we can add '1' to the // string (oneCount < K2) if (oneCount < K2 && i == 1) { res2 = countValidString(zeroCount, oneCount + 1, K1, K2, n - 1); } // Add '2' to the string res3 = countValidString(zeroCount, 0, K1, K2, n - 1); } // Return the sum modulo 'mod' return (res1 + res2 + res3) % mod;}// Drivers codeint main(){ int n = 2, K1 = 1, K2 = 2; // Call the solve function to calculate // the valid strings cout << countValidString(0, 0, K1, K2, n); return 0;} |
Output
8
Time Complexity: O(3^n), where ‘n’ is the length of the string.
Auxiliary Space: O(n)
Counting valid strings that contains ‘0’, ‘1’, or ‘2’ using Dynamic Programming (Memoization):
Explore the valid string using recursion and memoize the subproblems. The state includes the counts of ‘0’s and consecutive ‘1’s, and recursion explores character choices (‘0’, ‘1’, ‘2’) for valid strings, we also keep maintain the constraints like no more than K1 ‘0’ and no K2 consecutive ‘1’s. Finally, add valid answers to result and return the result by taking modulo.
Step-by-step approach:
- Use a three dimensional dp[zeroCount][oneCount][n1], which represents the result of subproblem when the count of zero was zeroCount, the count of one was oneCount for n1 length string.
- Base Case: When n becomes 0, this indicates that a valid string of the desired length has been generated. So, return 1.
- Within the countValidString() function, iterates over the three possible characters: ‘0’, ‘1’, and ‘2’. For each character, checks if it can be added to the string based on the constraints:
- If zeroCount < K1, we can add ‘0’ to the string. So, recur for rest of the length and store result in res1.
- If oneCount < K2, we can add ‘1’ to the string. So, recur for rest of the length and store result in res2.
- We can always add ‘2’ to the string. So, recur for rest of the length and store result in res3.
- Finally, store the overall result in dp before returning result = (res1 + res2 + res3) % 1e9+7.
Below is the implementation of the above approch:
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;// Define a 3D array for memoizationint dp[10][10][100005];// Define a modulo valueint mod = 1e9 + 7;// Recursive function to calculate the// number of valid stringsint countValidString(int zeroCount, int oneCount, int K1, int K2, int n){ // Base case: If n becomes 0, return 1 // as a valid record is found if (n == 0) return 1; // If the result for the current state // is already calculated, return it if (dp[zeroCount][oneCount][n] != -1) return dp[zeroCount][oneCount][n]; // Initialize variables to // store different results long long res1 = 0, res2 = 0, res3 = 0; // Iterate over three possible // characters: 0, 1, and 2 for (int i = 0; i <= 2; i++) { // Check if we can add '0' to // the string (zeroCount < K1) if (zeroCount < K1 && i == 0) { res1 = countValidString(zeroCount + 1, 0, K1, K2, n - 1); } // Check if we can add '1' to the // string (oneCount < K2) if (oneCount < K2 && i == 1) { res2 = countValidString(zeroCount, oneCount + 1, K1, K2, n - 1); } // Add '2' to the string res3 = countValidString(zeroCount, 0, K1, K2, n - 1); } // Store the result in the memoization // table and return the sum modulo 'mod' return dp[zeroCount][oneCount][n] = (res1 + res2 + res3) % mod;}// Drivers codeint main(){ int n = 1012, K1 = 3, K2 = 5; // Initialize the memoization table with -1 memset(dp, -1, sizeof(dp)); // Call the solve function to calculate // the valid strings cout << countValidString(0, 0, K1, K2, n); return 0;} |
Output
663818944
Time Complexity: O(N)
Auxiliary Space: O(N*K1*K2)
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!
