Start learning free

LESSON 314 OF 347 · DYNAMIC PROGRAMMING

Binary Strings of Given Length in C#: A First DP Table

Practice O(n) Read the full explanation

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
    Ctrl + Enter to check

    C# · DYNAMIC PROGRAMMING

    Binary Strings Of Given Length in C#, explained

    Problem overview

    The method CountBinaryStrings receives an integer n and returns how many binary strings of length n exist. A binary string uses only the characters 0 and 1. For n = 3 there are 8 of them: 000, 001, 010, 011, 100, 101, 110 and 111. The notes say n is at most 30.

    The strings themselves aren't needed, only their number, so the task is a counting problem and a good first look at dynamic programming.

    Approach: extend shorter strings by one bit

    Every string of length i is a string of length i - 1 followed by one more character. That last character is either 0 or 1, and both choices work for every shorter string, so each shorter string produces exactly two longer ones. The count doubles with each extra character:

    • length 1 has 2 strings: "0" and "1";
    • length 2 has 2 * 2 = 4;
    • length 3 has 2 * 4 = 8.

    Dynamic programming stores these answers in a table, dp, where dp[i] is the answer for length i. Each entry is computed from the one before it, starting from a base case that is known without computing.

    The table is not strictly needed here: the answer is simply 2 to the power n. The array makes the recurrence visible, and the same table-filling pattern appears in the harder problems that follow.

    Here is the growth for n = 3, written out. From the strings of length 2 (00, 01, 10, 11), appending 0 gives 000, 010, 100 and 110, and appending 1 gives 001, 011, 101 and 111. The two groups don't overlap, because they differ in the last character, and together they cover every string of length 3. That is why doubling is exact and no string is counted twice or missed.

    The same argument works from the other side. Each of the n positions is an independent choice between two characters, so there are 2 * 2 * ... * 2 strings, one factor per position. The table and the product describe the same count.

    Step by step

    1. Create the table. An int[] of size n + 1 has an index for every length from 0 to n. A new int array starts filled with zeros.
    2. Set the base case. dp[1] is 2, the strings "0" and "1".
    3. Loop from 2 up to n inclusive, so every shorter length is filled before the longer one that needs it.
    4. Double the previous entry: dp[i] = dp[i - 1] * 2.
    5. Return dp[n].

    The solution in C#

    class Solution {

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

    C# details worth knowing:

    • Array size and the last index. new int[n + 1] has indices 0 to n. The loop condition i <= n must reach n, and < would leave dp[n] as 0.
    • Fits in an int. For n = 30 the result is 1,073,741,824, below the int maximum of 2,147,483,647. At n = 31 it would reach 2,147,483,648 and the multiplication would wrap silently to a negative number, because C# doesn't check int overflow by default. The limit of 30 exists for this reason.
    • Index errors throw. Reading or writing outside an array throws IndexOutOfRangeException. With n = 0 the array has only index 0, so dp[1] = 2 throws. The notes don't promise that 0 is never passed, so a guard such as returning 1 for n = 0 (the empty string) would make the method safe.

    Reading the table

    For n = 5 the finished table is [0, 2, 4, 8, 16, 32]. Index 0 stays 0 because the code never sets it, and the answer is the last entry, 32. Printing the table while you learn dynamic programming is a good habit: every entry should be explainable from the one before it.

    Edge cases and common mistakes

    • Length 1. The loop doesn't run, and the method returns dp[1], which is 2.
    • Length 0. There is exactly one empty string, so the mathematically correct answer is 1, but the code above doesn't handle that case.
    • Loop bound. Using i < n returns 0 for lengths of 2 or more.
    • Starting the loop at 1. That would double dp[0], which is 0, and overwrite the base case with 0.

    Testing

    • n = 1 gives 2.
    • n = 3 gives 8.
    • n = 30 gives 1073741824.
    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