Start learning free

LESSON 319 OF 348 · DYNAMIC PROGRAMMING

Binary Strings With K Ones in TypeScript: 2D DP and Pascal's Triangle

Practice O(n * k) Read the full explanation

Given two non-negative integers N and K, return the number of binary strings of length N with exactly K ones

Example:

Input: N = 4, K = 2
Output: 6
Explanation: [
    "1100",
    "1010",
    "1001",
    "0110",
    "0101",
    "0011"
]
Notes: K <= N <= 30
STEP 1 OF 7
    Ctrl + Enter to check

    TYPESCRIPT · DYNAMIC PROGRAMMING

    Binary Strings With K Ones in TypeScript, explained

    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 contain exactly k characters equal to 1.

    For n = 4 and k = 2 there are six: 1100, 1010, 1001, 0110, 0101 and 0011. The answer is 6. Only the count is needed.

    Approach: a table indexed by length and number of ones

    Two numbers describe a subproblem: the length of the string and the number of ones it must contain. So the table has two dimensions. Let dp[i][j] be the number of binary strings of length i with exactly j ones.

    To find dp[i][j], look at the last character of such a string and remove it:

    • If it is a 0, the remaining i - 1 characters still hold all j ones: dp[i - 1][j] strings.
    • If it is a 1, the remaining i - 1 characters hold j - 1 ones: dp[i - 1][j - 1] strings.

    Every string falls into exactly one group, so dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]. This is the rule that builds Pascal's triangle: each entry is the sum of the one above it and the one above-left. The value dp[n][k] is therefore the binomial coefficient "n choose k".

    The base cases are:

    • dp[0][0] = 1: the empty string has zero ones, and there is one such string.
    • dp[i][0] = 1: the only string of length i without ones is all zeros.

    Entries where j is larger than i stay 0, because a string can't have more ones than characters. For n = 4 and k = 2 the table grows row by row. Row 2 is 1, 2, 1, row 3 is 1, 3, 3 and row 4 is 1, 4, 6, and the 6 in the last row is the answer.

    A quick check on the example: the 6 strings split by their last character. Those ending in 0 are 1100, 1010 and 0110, three strings, matching dp[3][2] = 3 (the strings of length 3 with two ones: 110, 101, 011). Those ending in 1 are 1001, 0101 and 0011, also three, matching dp[3][1] = 3 (100, 010, 001). Together that is 3 + 3 = 6.

    Step by step

    1. Declare dp as a const number[][] with n + 1 rows. Loop over i from 0 to n and give every row k + 1 zeros.
    2. Set dp[0][0] to 1, the empty string.
    3. Open the outer loop with i from 1 to n inclusive, filling the table one length at a time.
    4. Set dp[i][0] to 1 for the all-zeros string. The inner loop starts at j = 1, so it never reaches column 0.
    5. Open the inner loop with j from 1 to k inclusive.
    6. Add the two cases: dp[i - 1][j] for a last character 0 and dp[i - 1][j - 1] for a last character 1.
    7. Return dp[n][k].

    The solution in TypeScript

    class Solution {

    countBinaryStrings(n: number, k: number): number {
        const 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 = 1; i <= n; i++) {
            dp[i][0] = 1;
            for (let j = 1; j <= k; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
            }
        }
        return dp[n][k];
    }
}

    TypeScript details worth knowing:

    • A table is an array of arrays. TypeScript has no built-in two-dimensional array. dp[i][j] first picks row i, then column j inside it.
    • Each row must be its own array. The loop creates a new array per row. Writing new Array(n + 1).fill(new Array(k + 1).fill(0)) would put the same inner array in every slot, since fill reuses one value, and a change to one row would show in all of them. Using fill(0) on the inner array is safe, because 0 is a number and is copied.
    • The outer array is only partly filled until the loop runs. new Array(n + 1) makes empty slots; the first loop writes every one of them before the table is read.
    • Inner arrays have k + 1 columns, so the valid column indices are 0 to k. That is why the inner loop's condition is j <= k.
    • Doubles, no overflow. The largest answer in range, for n = 30 and k = 15, is 155,117,520, which a number holds exactly.

    Complexity

    Time: O(n * k). Building the table touches each of its (n + 1) * (k + 1) cells a constant number of times.

    Space: O(n * k). The table is the memory. Row i only depends on row i - 1, so keeping just two rows would bring it down to O(k).

    Edge cases and common mistakes

    • k = 0. The inner loop doesn't run, every row keeps its dp[i][0] = 1, and the answer is 1: all zeros.
    • k = n. The answer is 1: all ones. For n = 3 and k = 3 the table gives dp[3][3] = 1.
    • n = 0. With k = 0 the table is a single cell holding 1, so the answer is 1.
    • Forgetting dp[i][0] = 1. The inner loop starts at 1, so column 0 stays 0 for every row except row 0, and all the sums downstream come out too small.
    • Reading column j - 1 when j = 0. That would be index -1, which on an array is just a missing property and gives undefined, not an error. The loop avoids it by starting at j = 1.
    • Sharing one row between all rows. See the fill note above; the symptom is a table whose rows are all identical.

    Testing

    • n = 4, k = 2 gives 6.
    • n = 5, k = 0 gives 1.
    • n = 3, k = 3 gives 1.
    • n = 0, k = 0 gives 1.
    • n = 30, k = 15 gives 155117520.
    Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free