leetcode

// 2466. Count Ways To Build Good Strings
#include "leetcode.h"

/*
 * 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 opperations:
 * - 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. return modulo 10^9+7.
 */

int countGoodStrings(int low, int high, int zero, int one) {
  int mod = 1e9 + 7, ans = 0;
  int *dp = (int *)calloc(high + 1, sizeof(int));
  dp[0] = 1;
  for (int i = 1; i <= high; i++) {
    if (i >= one)
      dp[i] = (dp[i] + dp[i - one]) % mod;
    if (i >= zero)
      dp[i] = (dp[i] + dp[i - zero]) % mod;
    if (i >= low)
      ans = (ans + dp[i]) % mod;
  }
  free(dp);
  return ans;
}

int main() {
  printf("%d\n", countGoodStrings(3, 3, 1, 1)); // expect: 8
  printf("%d\n", countGoodStrings(2, 3, 1, 2)); // expect: 5
}