source: https://leetcode.com/problems/count-ways-to-build-good-strings/description/

### Count Ways To Build Good Strings

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 10^9 + 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

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 |
class Solution { public int countGoodStrings(int low, int high, int zero, int one) { Integer[] memo = new Integer[high+1]; return dfs(0, low, high, zero, one, memo); } private static final int MOD = 1_000_000_007; public int dfs(int length, int low, int high, int zero, int one, Integer[] memo){ if(length>high){ return 0; } if(memo[length]!=null) return memo[length]; long count = 0; if(length >= low && length <= high){ count = count+1; } //either append zero count = (count + dfs(length+zero, low, high, zero, one, memo))%MOD; //or append one count = (count + dfs(length+one, low, high, zero, one, memo))%MOD; memo[length] = (int)count; return (int)count; } } |