Start learning free

LESSON 317 OF 347 · DYNAMIC PROGRAMMING

Binary Strings Without Consecutive Ones in C#: Fibonacci 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

    C# · DYNAMIC PROGRAMMING

    Binary Strings Without Consecutive Ones in C#, explained

    Problem overview

    The method CountBinaryStrings receives an integer n and returns how many binary strings of length n contain no two adjacent 1s. For n = 3 the answer is 5: 000, 001, 010, 100 and 101. The other three strings of length 3, namely 011, 110 and 111, each contain "11". The notes say n is at most 30.

    Approach: look at how a valid string ends

    Counting by listing every string would take 2 to the power n steps. Dynamic programming counts them by building on shorter results. Let dp[i] be the number of valid strings of length i, and ask how a valid string of length i can end:

    • It ends in 0. The first i - 1 characters can be any valid string, since a 0 can't create a "11". That gives dp[i - 1] strings.
    • It ends in 1. The character before that 1 must be 0, otherwise "11" appears. So the string ends in "01", and the first i - 2 characters can be any valid string. That gives dp[i - 2] strings.

    Those two cases cover all valid strings and don't overlap, so dp[i] = dp[i - 1] + dp[i - 2]. That is the Fibonacci recurrence.

    It needs two starting values. The empty string is valid, so dp[0] = 1. Both "0" and "1" are valid, so dp[1] = 2. Then dp[2] = 3 (00, 01, 10), dp[3] = 5, dp[4] = 8 and so on.

    Step by step

    1. Create the table: an int[] named dp of length n + 1, zero-filled by default.
    2. Set the base cases: dp[0] = 1 and dp[1] = 2.
    3. Loop from 2 while i <= n, so each entry builds on the two before it and the loop reaches dp[n].
    4. Add the two cases: dp[i] = dp[i - 1] + dp[i - 2].
    5. Return dp[n].

    The solution in C#

    class Solution {

    public int CountBinaryStrings(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 2;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

    C# details worth knowing:

    • Two base cases need room. dp[1] requires an array of at least two elements, so n must be at least 1. With n = 0, new int[1] has only index 0 and the assignment dp[1] = 2 throws IndexOutOfRangeException. The mathematically correct answer for n = 0 is 1 (the empty string), so a guard would make the method safe for it.
    • Size of the answer. dp[30] is 2,178,309, comfortably inside an int. The values grow by roughly a factor of 1.6 per step, much slower than the 2 per step of all binary strings.
    • Zero-filled arrays. C# initializes every element of a new int[] to 0, so entries from 2 up are overwritten before they are read.

    Complexity

    Time: O(n), one pass with a single addition per step. Space: O(n) for the table. Since each entry uses only the previous two, two variables would be enough for O(1) space.

    Edge cases and common mistakes

    • n = 1. The loop doesn't run and the method returns 2.
    • n = 2. The answer is 3: only "11" is excluded.
    • Forgetting the "01" detail. A common mistake is to say a string ending in 1 has dp[i - 1] choices before it. That would allow another 1 right before it. The 1 must be preceded by a 0, which is why the count is dp[i - 2].
    • Wrong dp[0]. If it is 0, then dp[2] comes out as 2 instead of 3. The empty string is a legitimate prefix for the string "01".
    • Loop bound. Using i < n leaves dp[n] at 0.

    Testing

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