LESSON 315 OF 348 · DYNAMIC PROGRAMMING

Binary Strings of Given Length in TypeScript: Counting with DP

Given a non-negative integer N return the number of binary strings of length N

Example:

Input: N = 3
Output: 8
Explanation: [
    "000",
    "001",
    "010",
    "011",
    "100",
    "101",
    "110",
    "111"
]

Notes: N <= 30

STEP 1 OF 5

Guided

Ctrl + Enter to check

Binary Strings Of Given Length in TypeScript, explained

Problem overview

The method countBinaryStrings receives a non-negative integer n and returns how many strings of length n can be written with the characters 0 and 1. For n = 3 there are eight: 000, 001, 010, 011, 100, 101, 110 and 111, so the answer is 8. The statement limits n to 30.

Only the count is needed, not the strings themselves. That matters, because listing them would take a number of steps proportional to the answer, while counting can be done in a handful of steps.

Approach: each bit doubles the count

Look at how a string of length i is made: take a string of length i - 1 and add one more character, either 0 or 1. Every shorter string can be extended in exactly two ways, and different shorter strings or different final characters never produce the same longer string. So the number of strings of length i is twice the number of length i - 1.

That is a recurrence, dp[i] = 2 * dp[i - 1], with a base case: there are two strings of length 1, "0" and "1". This is dynamic programming in its simplest form: store the answer for each length, and build the next from the previous one. The values go 2, 4, 8, 16, and in closed form the answer is 2 to the power n. The table is kept in the lesson because it shows the recurrence directly, and the same shape returns in the harder problems of this chapter.

Step by step

Declare the table dp, a number[] with n + 1 entries so that index n exists. Entry i will hold the count for length i.
Set the base case: dp[1] is 2.
Loop with i from 2 up to and including n, so each length is computed after the one before it.
Double: dp[i] is dp[i - 1] * 2.
Return dp[n], the count for the full length.

The solution in TypeScript

class Solution {
    countBinaryStrings(n: number): number {
        let dp: number[] = new Array(n + 1);
        dp[1] = 2;
        for (let i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] * 2;
        }
        return dp[n];
    }
}

TypeScript details worth knowing:

new Array(n + 1) makes empty slots, not zeros. Reading a slot that was never written gives undefined. This is fine here, because the loop writes every slot before it reads it. When you need zeros, use new Array(n + 1).fill(0).
The annotation number[] only helps the compiler. It disappears when the code is compiled to JavaScript, and it doesn't fill the array with anything.
No overflow. A number is a double, so there is no integer wrap-around. For n = 30 the answer is 1,073,741,824, far below the point (2 to the power 53) where integers stop being exact.
let versus const. dp is never reassigned, so const would be the more usual choice, as in the other lessons of this chapter. The code behaves the same either way.

Complexity

Time: O(n). The loop runs n - 1 times and each pass does one multiplication.

Space: O(n). The table has n + 1 entries. Since each value depends only on the previous one, a single running variable would reduce the space to O(1).

Edge cases and common mistakes

n = 1. The loop doesn't run and the answer is dp[1], which is 2.
n = 0. Mathematically there is one string of length 0, the empty string, so the answer should be 1. This solution doesn't handle it: it creates an array with a single slot, then dp[1] = 2 grows the array, and dp[0] is never written, so it returns undefined. Starting the table at dp[0] = 1 fixes this. The lesson's tests pass with the code as it is, so this is worth knowing but not required here.
Stopping the loop one early. With i < n the last entry is never computed, and the function returns undefined for n greater than 1.
Starting the loop at 1. It would compute dp[1] from the unset dp[0], and undefined * 2 is NaN.
Counting by listing. Building every string works for small n, but for n = 30 there are over a billion of them.

Testing

n = 1 gives 2.
n = 2 gives 4.
n = 3 gives 8.
n = 30 gives 1073741824.

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

Start learning free