Count Ways To Build Good Strings — LeetCode 2466 Python Solution

The problem

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.

Example

Input

low = 3, high = 3, zero = 1, one = 1

Output

8

Explanation

One possible valid good string is "011".

Python solution

class Solution:
    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:
        @cache
        def dfs(i):
            if i > high:
                return 0
            ans = 0
            if low <= i <= high:
                ans += 1
            ans += dfs(i + zero) + dfs(i + one)
            return ans % mod

        mod = 10**9 + 7
        return dfs(0)

Complexity

Pattern: Dynamic Programming

Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 2466. Count Ways To Build Good Strings is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.

The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.

Related problems