Sponsored
Sponsored
We can solve this problem using a dynamic programming approach. The idea is to maintain a dp array where dp[i] represents the number of good strings of exact length i. Start with an empty string and attempt to form strings by appending '0's and '1's zero and one times respectively. For each length from low to high, we incrementally calculate the number of ways to achieve that length from smaller lengths and store them in dp[i].
Time Complexity: O(high)
Space Complexity: O(high)
1using System;
2
3class Program {
4 const int MOD = 1000000007;
5
6 static int CountGoodStrings(int low, int high, int zero, int one) {
7 int[] dp = new int[high + 1];
8 dp[0] = 1;
9 for (int i = 1; i <= high; i++) {
10 if (i >= zero) dp[i] = (dp[i] + dp[i - zero]) % MOD;
11 if (i >= one) dp[i] = (dp[i] + dp[i - one]) % MOD;
12 }
13 int result = 0;
14 for (int i = low; i <= high; i++) {
15 result = (result + dp[i]) % MOD;
16 }
17 return result;
18 }
19
20 static void Main() {
21 Console.WriteLine(CountGoodStrings(3, 3, 1, 1));
22 }
23}The C# solution uses a similar structure as the other solutions. An integer array dp is used to keep track of possible strings of each length. The method CountGoodStrings computes and returns the sum of valid string counts from low to high.
In this approach, we explore every possible string configuration using backtracking to find strings whose lengths fall between low and high. We use recursion to build strings by appending zero or one '0's and '1's, tracking lengths and adding valid ones to a result set. Although not as efficient as the DP method due to exponential complexity, it serves as an insightful means to intuitively grasp the construction of such strings.
Time Complexity: O(2^n) where n is high / min(zero, one)
Space Complexity: O(n) because of the recursion stack
1def countGoodStrings(low, high, zero, one):
2 MOD =
The backtracking solution in Python employs a recursive function to consider adding either zero or one characters to a string. It tracks the length of each created string and counts those which are valid. Once a length exceeds high, recursion stops further exploration from that branch.