Description
You are given 3 positive integers num_zeros, num_ones, and limit.
A binary array arr is called stable if:
- The number of occurrences of 0 in
arris exactlynum_zeros. - The number of occurrences of 1 in
arris exactlynum_ones. - Each subarray of
arrwith a size greater thanlimitmust contain at least one occurrence of both 0 and 1.
Return an integer denoting the total number of stable binary arrays.
Since the answer may be very large, return it modulo 109 + 7.
Example 1:
Input: zero = 1, one = 1, limit = 2
Output: 2
Explanation:
The two possible stable binary arrays are [1,0] and [0,1], as both arrays have a single 0 and a single 1, and no subarray has a length greater than 2.
Example 2:
Input: zero = 1, one = 2, limit = 1
Output: 1
Explanation:
The only possible stable binary array is [1,0,1].
Note that the binary arrays [1,1,0] and [0,1,1] have subarrays of length 2 with identical elements, hence, they are not stable.
Example 3:
Input: zero = 3, one = 3, limit = 2
Output: 14
Explanation:
All the possible stable binary arrays are [0,0,1,0,1,1], [0,0,1,1,0,1], [0,1,0,0,1,1], [0,1,0,1,0,1], [0,1,0,1,1,0], [0,1,1,0,0,1], [0,1,1,0,1,0], [1,0,0,1,0,1], [1,0,0,1,1,0], [1,0,1,0,0,1], [1,0,1,0,1,0], [1,0,1,1,0,0], [1,1,0,0,1,0], and [1,1,0,1,0,0].
Constraints:
1 <= zero, one, limit <= 200
Solutions
This uses dynamic programming where dp[i][j][k] represents the number of valid strings using exactly i zeros and j ones, ending with digit k (0 or 1). It initializes base cases for strings ending at the limit, then fills the table by computing transitions: when adding more of a digit than the limit allows, it subtracts out the invalid cases using inclusion-exclusion principle. The modulo operations handle the large number of possibilities while keeping results within bounds.
/**
* @param {number} zero
* @param {number} one
* @param {number} limit
* @return {number}
*/
var numberOfStableArrays = function (zero, one, limit) {
const MOD = 1000000007;
const dp = Array.from({ length: zero + 1 }, () =>
Array.from({ length: one + 1 }, () => [0, 0]),
);
for (let i = 0; i <= Math.min(zero, limit); i++) {
dp[i][0][0] = 1;
}
for (let j = 0; j <= Math.min(one, limit); j++) {
dp[0][j][1] = 1;
}
for (let i = 1; i <= zero; i++) {
for (let j = 1; j <= one; j++) {
if (i > limit) {
dp[i][j][0] =
dp[i - 1][j][0] + dp[i - 1][j][1] - dp[i - limit - 1][j][1];
} else {
dp[i][j][0] = dp[i - 1][j][0] + dp[i - 1][j][1];
}
dp[i][j][0] = ((dp[i][j][0] % MOD) + MOD) % MOD;
if (j > limit) {
dp[i][j][1] =
dp[i][j - 1][1] + dp[i][j - 1][0] - dp[i][j - limit - 1][0];
} else {
dp[i][j][1] = dp[i][j - 1][1] + dp[i][j - 1][0];
}
dp[i][j][1] = ((dp[i][j][1] % MOD) + MOD) % MOD;
}
}
return (dp[zero][one][0] + dp[zero][one][1]) % MOD;
};