Leetcode problem solution: 2466. Count Ways To Build Good Strings

index.ts

// Problem: https://leetcode.com/problems/count-ways-to-build-good-strings/description/

const MOD = 1e9 + 7;

function countGoodStrings(low: number, high: number, zero: number, one: number): number {
  return count(0, low, high, zero, one, new Array(high+1));
};

function count(len: number, low: number, high: number, zero: number, one: number, cache: number[]): number {
  // In case, current length is higher than highest allowed length,
  // we should leave the function.
  if (len > high) {
    return 0;
  }

  // Take cache value in case it exists.
  if (cache[len] !== undefined) {
    return cache[len];
  }

  // In both of the next cases we should keep computing
  // the required value by imagining we are adding zeroes
  // or ones to current string.
  // We add 1 assumptioning that current string is valid
  // and we found one more solution. 
  cache[len] = (low <= len && len <= high ? 1 : 0) 
    + count(len + zero, low, high, zero, one, cache) 
    + count(len + one, low, high, zero, one, cache);

  return cache[len] % MOD;
}