Problem overview
The method countBinaryStrings receives two non-negative integers, n and k, with k <= n <= 30. It returns how many binary strings of length n never contain more than k ones in a row.
For n = 4 and k = 2 the answer is 13. There are 16 binary strings of length 4, and exactly three break the rule: "0111", "1110" and "1111", each of which has a run of three ones.
Approach: count strings by how they end
Generating all 2^n strings and checking each one works for small n, but with n up to 30 that means over a billion strings. We only need a count, so we can count without generating.
The idea is dynamic programming. Build the strings one character at a time, and keep track only of what matters for the next decision: how many ones the string currently ends with. Let dp[i][j] be the number of valid strings of length i that end in exactly j consecutive ones, with j between 0 and k.
From a valid string counted in dp[i][j], there are two ways to add a character:
- Append a 0. The run of ones is broken, so the new string, of length
i + 1, ends in zero ones. The count goes intodp[i + 1][0]. This is always allowed. - Append a 1. The run grows to
j + 1. This is only allowed whenj < k, otherwise the string would have more thankconsecutive ones. The count goes intodp[i + 1][j + 1].
Every valid string of length i + 1 comes from exactly one valid string of length i by one of these moves, so nothing is counted twice or missed. The starting point is the empty string: one string of length 0, ending in zero ones, so dp[0][0] = 1. The answer is the sum of the last row, dp[n][0] through dp[n][k].
Check with n = 3 and k = 1, where no two ones may touch. Row 0 is [1, 0]. Row 1 is [1, 1]: the strings "0" and "1". Row 2 is [2, 1]: the strings "00", "10" and "01". Row 3 is [3, 2], and the total is 5. The valid strings are 000, 001, 010, 100 and 101.
Step by step
- Create the outer array
dpwithn + 1slots, one per possible length from 0 ton.new Array(n + 1)only reserves empty slots, and the rows come next. - Fill each slot with a fresh row of
k + 1zeros, usingnew Array(k + 1).fill(0)inside a loop. Each row must be a new array. If one row were shared, every row would change together. - Set
dp[0][0]to 1. The empty string is the single valid string of length 0. - Loop over lengths
ifrom 0 ton - 1. The body writes into rowi + 1, and the last row isn, so the loop stops one short. - Loop over trailing-ones counts
jfrom 0 tok, inclusive, because a valid string can end in any number of ones up tok. - Add
dp[i][j]intodp[i + 1][0]. This is the "append a 0" move. Use+=, because everyjfeeds the same cell. - Guard the "append a 1" move with
if (j < k), and inside it adddp[i][j]intodp[i + 1][j + 1]. - Declare
resultas 0 below the nested loops. Declared inside a loop, it would be reset on every pass. - Add every
dp[n][j]toresultin a loop overjfrom 0 tok. - Return
result.
The solution in TypeScript
class Solution {
countBinaryStrings(n: number, k: number): number {
let dp: number[][] = new Array(n + 1);
for (let i = 0; i <= n; i++) {
dp[i] = new Array(k + 1).fill(0);
}
dp[0][0] = 1;
for (let i = 0; i < n; i++) {
for (let j = 0; j <= k; j++) {
dp[i + 1][0] += dp[i][j];
if (j < k) {
dp[i + 1][j + 1] += dp[i][j];
}
}
}
let result: number = 0;
for (let j = 0; j <= k; j++) {
result += dp[n][j];
}
return result;
}
}
TypeScript details worth a look:
new Array(n + 1)makes holes, not values. The slots are empty, notundefinedor 0, until you assign them. That is why the second step writes every row before it is read.- Shared rows are a real trap.
new Array(3).fill(new Array(2).fill(0))puts the same inner array in all three slots. Settingrows[0][0] = 1then shows up in every row. Creating the row inside the loop avoids that. - The type annotation checks nothing at run time.
number[][]tells the compiler what to expect, butnew Array(...)returnsany[], so the compiler would accept almost anything stored in it. numberis a double. The largest answer here is forn = 30,k = 30, which is 2^30 = 1,073,741,824. That is far below the 2^53 limit for exact integers, so the sums are exact.
Complexity
Time: O(n * k). The nested loops run n times over k + 1 values of j, and each step does constant work. Summing the last row costs O(k).
Space: O(n * k). The table has n + 1 rows of k + 1 cells. Row i + 1 depends only on row i, so two rows would be enough, but this lesson keeps the whole table for clarity.
Edge cases and common mistakes
n = 0. The loops over lengths never run, and the sum of row 0 is 1: the empty string.countBinaryStrings(0, 0)returns 1.k = 0. No ones are allowed, so the only valid string is all zeros. Each row has a single cell, the guardj < kis never true, andcountBinaryStrings(3, 0)returns 1.k = n. Every string is valid, and the answer is2^n. Forn = 30that is 1,073,741,824.- Writing
j <= kin the guard. The row has onlyk + 1cells, sodp[i + 1][k + 1]would go outside it, and the check on the run length would be lost. - Looping
iup ton. The last iteration would write todp[n + 1], which does not exist, and fail with aTypeError. - Forgetting the base case. Without
dp[0][0] = 1, every cell stays 0 and the answer is 0.
Testing
countBinaryStrings(4, 2)gives 13.countBinaryStrings(3, 1)gives 5.countBinaryStrings(3, 0)gives 1.countBinaryStrings(1, 1)gives 2.countBinaryStrings(30, 30)gives 1073741824.