2466. Count Ways To Build Good Strings

// Approach: DP counting strings of each length; sum lengths in [low, high].
// Time: O(high) Space: O(high)

public class Solution
{
    public int CountGoodStrings(int low, int high, int zero, int one)
    {
        const int kMod = 1_000_000_007;
        int ans = 0;
        // dp[i] := the number of good strings with length i
        int[] dp = new int[high + 1];
        dp[0] = 1;

        for (int i = 1; i <= high; ++i)
        {
            if (i >= zero)
                dp[i] = (dp[i] + dp[i - zero]) % kMod;
            if (i >= one)
                dp[i] = (dp[i] + dp[i - one]) % kMod;
            if (i >= low)
                ans = (ans + dp[i]) % kMod;
        }

        return ans;
    }
}