Start learning free

LESSON 318 OF 348 · DYNAMIC PROGRAMMING

Binary Strings Without Consecutive Ones in TypeScript: DP

Practice O(n) Read the full explanation

Given a non-negative integer N return the number of binary strings of length N without 2 consecutive ones

Example:

Input: N = 3
Output: 5
Explanation: [
    "000",
    "001",
    "010",
    "100",
    "101",
]
Notes: N <= 30
STEP 1 OF 5
    Ctrl + Enter to check

    TYPESCRIPT · DYNAMIC PROGRAMMING

    Binary Strings Without Consecutive Ones in TypeScript, explained

    Problem overview

    The method countBinaryStrings receives a non-negative integer n and returns how many binary strings of length n contain no two 1 characters next to each other. For n = 3 there are eight strings in total, and three of them are excluded: 011, 110 and 111. The five that remain are 000, 001, 010, 100 and 101, so the answer is 5. The statement limits n to 30.

    Approach: look at how a valid string ends

    Checking all 2^n strings is far too slow for n = 30. Instead, count the valid strings of each length from the shorter ones. Look at the end of a valid string of length i:

    • If it ends in 0, whatever comes before it can be any valid string of length i - 1. A zero can't create a pair of ones. That gives dp[i - 1] strings.
    • If it ends in 1, the character before must be 0, or the string would end in 11. So it ends in 01, and the part before those two characters is any valid string of length i - 2. That gives dp[i - 2] strings.

    These two groups don't overlap and cover every valid string, so

    dp[i] = dp[i - 1] + dp[i - 2]

    This is the Fibonacci recurrence. The base cases are dp[0] = 1, the empty string, and dp[1] = 2, the strings "0" and "1", neither of which can contain two consecutive ones. The table runs 1, 2, 3, 5, 8, and dp[3] = 5 matches the example.

    Step by step

    1. Declare dp as a const array of numbers with n + 1 slots, so each index can hold the count for that length.
    2. Store the base cases: 1 string of length 0 and 2 of length 1.
    3. Loop with i from 2 through n. Each new count depends on the two before it, so they must be ready first.
    4. Add the previous two entries: a valid string ends either in 0 or in 01.
    5. Return the last entry, dp[n], which holds the answer for the full length.

    The solution in TypeScript

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

    TypeScript details worth knowing:

    • const with an array that is filled later. const fixes the binding, not the contents, so assigning dp[0] and the other entries is allowed.
    • new Array(size) has empty slots. Reading one that was never written gives undefined. Every entry the loop reads has been written before, so the code is safe.
    • Writing past the length grows the array. With n = 0 the array starts with one slot, and dp[1] = 2 extends it to two. The answer dp[0] is still the right one, 1. JavaScript arrays resize when you write beyond their end.
    • Doubles, no overflow. The answer for n = 30 is 2,178,309, nowhere near the limit where integers stop being exact.
    • Annotations are erased when compiled to JavaScript; number[] exists for the compiler only.

    Complexity

    Time: O(n). The loop runs n - 1 times with one addition each.

    Space: O(n). The table has n + 1 entries. Each value needs only the previous two, so two variables would be enough for O(1).

    Edge cases and common mistakes

    • n = 0. The answer is 1, the empty string, as set by the base case.
    • n = 1. The answer is 2: both 0 and 1 are valid.
    • n = 2. Of 00, 01, 10 and 11, only 11 is excluded, so the answer is 3, which is dp[1] + dp[0].
    • Using dp[i - 2] for the 1 ending without the zero. The ending 01 uses two characters, which is why the rest has length i - 2, not i - 1.
    • Counting 10 and 01 ending separately. A valid string may end in 10, but that case is already part of "ends in 0" and counted in dp[i - 1].
    • Missing base case dp[0]. Then dp[2] becomes 2 + undefined, which is NaN, and every later entry is NaN too.

    Testing

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