2466. Count Ways To Build Good Strings
Description
Given the integers zero
, one
, low
, and high
, we can construct a string by starting with an empty string, and then at each step perform either of the following:
- Append the character
'0'
zero
times. - Append the character
'1'
one
times.
This can be performed any number of times.
A good string is a string constructed by the above process having a length between low
and high
(inclusive).
Return the number of different good strings that can be constructed satisfying these properties. Since the answer can be large, return it modulo 109 + 7
.
Example 1:
Input: low = 3, high = 3, zero = 1, one = 1 Output: 8 Explanation: One possible valid good string is "011". It can be constructed as follows: "" -> "0" -> "01" -> "011". All binary strings from "000" to "111" are good strings in this example.
Example 2:
Input: low = 2, high = 3, zero = 1, one = 2 Output: 5 Explanation: The good strings are "00", "11", "000", "110", and "011".
Constraints:
1 <= low <= high <= 105
1 <= zero, one <= low
Solutions
Solution 1: Memoization Search
We design a function $dfs(i)$ to represent the number of good strings constructed starting from the $i$-th position. The answer is $dfs(0)$.
The computation process of the function $dfs(i)$ is as follows:
- If $i > high$, return $0$;
- If $low \leq i \leq high$, increment the answer by $1$, then after $i$, we can add either
zero
number of $0$s orone
number of $1$s. Therefore, the answer is incremented by $dfs(i + zero) + dfs(i + one)$.
During the process, we need to take the modulus of the answer, and we can use memoization search to reduce redundant computations.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n = high$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
|