23.05.13 Today’s Leetcode

2466. Count Ways To Build Good Strings (medium)

Mathmatical Approach TLE at 26/36

class Solution:
    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:
        
        MOD = 10**9 + 7

        def help(k):
            temp = 0
            for i in range(k // zero + 1):
                left = k - i * zero
                if left % one == 0:
                    temp += math.factorial(left // one + i) // math.factorial(left // one) // math.factorial(i)
            return temp % MOD
        
        res = 0
        for i in range(low, high + 1):
            res += help(i)
        
        return res % MOD        

DP Approach

class Solution:
    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:
        dp = Counter({0: 1})
        mod = 10 ** 9 + 7
        for i in range(1, high + 1):
            dp[i] = (dp[i - one] + dp[i - zero]) % mod
        
        ans = sum(dp[i] for i in range(low, high + 1)) % mod
        return ans