Problem URL: Number of good binary strings

We will solve it using top-down dynamic programming. We will create a helper function dp that will return the number of good binary strings of length n and ending with end. Then we will return the number of good binary strings of length n. We will use memoization to avoid re-computation.

class Solution:
    def goodBinaryStrings(self, minLength: int, maxLength: int, oneGroup: int, zeroGroup: int) -> int:
        MOD = 10**9+7

        @cache
        def dp(i: int) -> int:
            if i > maxLength:
                return 0

            res = minLength <= i <= maxLength

            return (res + dp(i+oneGroup) + dp(i+zeroGroup)) % MOD

        return dp(0)

Time complexity: O(n)
Space complexity: O(n)