LESSON 320 OF 348 · DYNAMIC PROGRAMMING

Binary Strings With K Ones on Even Positions in TypeScript

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 placed only on even positions

Example:

Input: N = 6, K = 2
Output: 3
Explanation: [
    "101000",
    "100010",
    "001010"
]

Notes: 2 * K <= N <= 30

STEP 1 OF 8

Guided

Ctrl + Enter to check

TYPESCRIPT · DYNAMIC PROGRAMMING

Binary Strings With K Ones On Even Positions in TypeScript, explained

Problem overview

The method countBinaryStrings(n, k) counts the binary strings of length n that contain exactly k ones, where every one sits on an even position. Positions are numbered from 0, so the even positions are 0, 2, 4 and so on. Zeros can go anywhere.

For n = 6 and k = 2 the even positions are 0, 2 and 4. Choosing two of them for the ones gives 101000, 100010 and 001010, so the answer is 3. The notes promise 2 * k <= n, which means there is always room for the ones.

Approach: build strings one position at a time

You could generate every binary string of length n and test it, but there are 2^n of them, and n can be 30. Generating all of them would be over a billion strings.

Dynamic programming avoids this by counting instead of listing. Let dp[i][j] be the number of strings of length i that have exactly j ones, all on even positions. A string of length i + 1 comes from a string of length i by deciding the character at position i:

Append a 0. This is always allowed and leaves the number of ones unchanged, so dp[i][j] flows into dp[i + 1][j].
Append a 1. This is allowed only when i is even, and it raises the count from j to j + 1, so dp[i][j] also flows into dp[i + 1][j + 1]. We skip it once j has reached k, because more than k ones is never useful.

Each string is built in exactly one way, so the counts add up without double counting. The answer is dp[n][k].

Here is the table for n = 3 and k = 1. Each row lists the counts for 0 ones and 1 one:

length 0: [1, 0]
length 1: [1, 1]   position 0 is even: "0" and "1"
length 2: [1, 1]   position 1 is odd: only a 0 can be added
length 3: [1, 2]   position 2 is even: "100" and "001" have one 1

The answer, dp[3][1], is 2, matching the strings 100 and 001.

Step by step

Create the table. Push n + 1 rows, one for each length from 0 to n, and give each row k + 1 zeros, one for each possible number of ones.
Seed the base case. The empty string has zero ones, so dp[0][0] = 1. Every longer string grows from it.
Loop over positions i from 0 to n - 1. Each pass reads row i and writes row i + 1, so the last pass fills row n.
Loop over ones counts j from 0 to k, including k, so every reachable state passes its ways forward.
Append a zero. Add dp[i][j] to dp[i + 1][j] unconditionally.
Test whether a one fits. The position must be even and j must be below k.
Append a one. Add dp[i][j] to dp[i + 1][j + 1]. The check on j keeps j + 1 inside the row.
Return dp[n][k]: the strings of full length with exactly k ones.

The solution in TypeScript

class Solution {

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

Some TypeScript details worth knowing:

const fixes the name, not the contents. dp can never be assigned a different array, but push and assignments such as dp[0][0] = 1 still change it.
Every row must be its own array. new Array(k + 1).fill(0) runs once per loop pass, so the rows are separate. Writing new Array(3).fill(new Array(2).fill(0)) would put the same inner array in all three slots. After setting shared[0][1] = 5 on such a table, all rows print as [ 0, 5 ].
fill(0) matters. new Array(k + 1) alone creates empty slots, and adding to an empty slot gives NaN.
The annotations are only for the compiler. number[][] checks your code while you write it, but it disappears when TypeScript compiles to JavaScript.
No overflow worry here. A number is a double, and the largest answer for n = 30 is far below 2^53, so the counts stay exact.
=== in the condition. i % 2 === 0 compares without converting types, which is the usual TypeScript habit.

Complexity

Time: O(n * k). The two nested loops run n and k + 1 times, and each cell takes a constant amount of work.

Space: O(n * k). The table has (n + 1) * (k + 1) cells. Because row i + 1 only needs row i, two rows would be enough, but the full table makes the idea easier to follow.

Edge cases and common mistakes

k = 0. Only the all-zero string qualifies, so the answer is 1. For n = 6 and k = 0 the function returns 1.
More ones than even positions. n = 3 and k = 3 returns 0, since only positions 0 and 2 can hold a one. The notes exclude such inputs, but the table handles them.
Counting positions from 1. In "101000" the ones are at positions 0 and 2. Treating the first character as position 1 would make odd indices the allowed ones.
Stopping the j loop at k - 1. The zero transition must also run for j = k, or strings that already have all their ones would vanish.
Dropping the j < k test. Then the code writes to column k + 1, which the row doesn't have. JavaScript raises no error: it stretches the row and stores NaN there (adding to undefined gives NaN). The table no longer has the shape you declared, which is a bug waiting to happen.

Testing

n = 6, k = 2 gives 3.
n = 7, k = 2 gives 6: the even positions are 0, 2, 4 and 6, and there are 6 ways to pick two of the four.
n = 5, k = 3 gives 1: only 10101.
n = 30, k = 7 gives 6435.
n = 4, k = 0 gives 1.

Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free