Start learning free

LESSON 318 OF 347 · DYNAMIC PROGRAMMING

Binary Strings With K Ones in C#: 2D DP and Pascal's Triangle

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

Example:

Input: N = 4, K = 2
Output: 6
Explanation: [
    "1100",
    "1010",
    "1001",
    "0110",
    "0101",
    "0011"
]
Notes: K <= N <= 30
STEP 1 OF 7
    Ctrl + Enter to check

    C# · DYNAMIC PROGRAMMING

    Binary Strings With K Ones in C#, explained

    Problem overview

    The method CountBinaryStrings receives two integers, n and k, and returns how many binary strings of length n contain exactly k ones. For n = 4 and k = 2 the answer is 6: 1100, 1010, 1001, 0110, 0101 and 0011. The notes guarantee k <= n <= 30.

    Approach: a table with two dimensions

    One number isn't enough to describe a partial string: the length matters, and so does how many ones it holds. So the table has two indices. Let dp[i, j] be the number of binary strings of length i with exactly j ones.

    To find a rule, look at the last character of such a string:

    • It is 0. Dropping it leaves a string of length i - 1 that still has j ones: dp[i - 1, j] possibilities.
    • It is 1. Dropping it leaves a string of length i - 1 with j - 1 ones: dp[i - 1, j - 1] possibilities.

    The cases are disjoint and cover everything, so dp[i, j] = dp[i - 1, j] + dp[i - 1, j - 1]. This is the rule that builds Pascal's triangle, so dp[n, k] is the binomial coefficient "n choose k". That is also a sanity check: choosing which k of the n positions hold ones gives the same count.

    The starting values: the empty string has zero ones, so dp[0, 0] = 1. For any length i, the only string with no ones is all zeros, so dp[i, 0] = 1.

    For n = 4 and k = 2, the rows of the table (columns 0 to 2) are 1 0 0, then 1 1 0, then 1 2 1, then 1 3 3, and finally 1 4 6. The last row's last entry is 6.

    Step by step

    1. Declare the table as int[,] with n + 1 rows and k + 1 columns. C# fills it with zeros.
    2. Set dp[0, 0] = 1, the empty string.
    3. Loop over the lengths i from 1 to n inclusive. Row 0 is already done.
    4. Set dp[i, 0] = 1 inside the loop. The inner loop below starts at column 1 and never touches column 0.
    5. Loop over the counts of ones j from 1 to k inclusive.
    6. Add the two cases: dp[i, j] = dp[i - 1, j] + dp[i - 1, j - 1].
    7. Return dp[n, k].

    The solution in C#

    class Solution {

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

    C# details worth knowing:

    • Rectangular arrays. int[,] is a single block with a fixed number of rows and columns, created by new int[n + 1, k + 1] and indexed with a comma: dp[i, j]. A jagged array, int[][], is an array of arrays, indexed as dp[i][j], and each row must be created separately. Mixing the two syntaxes doesn't compile.
    • Zero-filled. Every cell starts at 0, so cells such as dp[1, 2], which would count strings with more ones than characters, correctly stay 0.
    • Row 0 stays as set. For j > 0, dp[0, j] is 0, since an empty string can't hold a one.
    • No overflow in range. The largest value allowed by the notes is "30 choose 15", which is 155,117,520, well within an int.

    Why the table is Pascal's triangle

    Write row i of the table as a list over j. Row 0 is 1, row 1 is 1 1, row 2 is 1 2 1, row 3 is 1 3 3 1: every entry is the sum of the entry above it and the entry above-left, which is exactly how Pascal's triangle is built. Entry j of row i is the number of ways to choose which j of the i positions hold the ones. The table has only k + 1 columns, so it cuts the triangle off at column k, which is all the answer needs.

    Because 1 is added at column 0 for every row, the left edge of the triangle is a column of ones, and when k = n the answer sits on the right edge, which is also 1.

    This also explains the symmetry you may notice: dp[n, k] equals dp[n, n - k]. Choosing the positions of the ones is the same as choosing the positions of the zeros. For n = 4, strings with one 1 and strings with three 1s are both counted as 4.

    Complexity

    Time: O(n * k), since each of the table's cells is computed once with a single addition. Space: O(n * k) for the table. Because row i only reads row i - 1, two rows would be enough if memory mattered.

    Edge cases and common mistakes

    • k = 0. The inner loop never runs and the answer is dp[n, 0], which is 1 (all zeros).
    • k = n. The answer is 1: all ones.
    • n = 0 (so k = 0). The loop doesn't run, and dp[0, 0] is 1 for the empty string.
    • Forgetting column 0. Without dp[i, 0] = 1, every cell would depend on zeros from column 0 and the whole table would stay at 0 apart from the start.
    • Reading column -1. The inner loop starts at 1 so that j - 1 is never negative. A negative index throws IndexOutOfRangeException.
    • Swapped dimensions. Declaring new int[k + 1, n + 1] would mean the loops go out of range whenever k < n.

    Testing

    • n = 4, k = 2 gives 6.
    • n = 5, k = 0 gives 1.
    • n = 5, k = 5 gives 1.
    • n = 30, k = 15 gives 155117520.
    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