LESSON 310 OF 338 · DYNAMIC PROGRAMMING

Binary Strings With K Ones in Go: A 2D DP Table

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

Guided

Ctrl + Enter to check

Binary Strings With K Ones in Go, explained

Problem overview

The function countBinaryStrings takes two int values, 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 lesson's notes say k <= n <= 30.

Approach: two parameters, so a table with two dimensions

The answer depends on both the length and the number of ones, so the table needs two indices: dp[i][j] is the number of binary strings of length i with exactly j ones.

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

If it is 0, the first i - 1 characters hold all j ones: that is dp[i-1][j] strings.
If it is 1, the first i - 1 characters hold j - 1 ones: that is dp[i-1][j-1] strings.

Every string falls in exactly one group, so dp[i][j] = dp[i-1][j] + dp[i-1][j-1]. This is the rule that builds Pascal's triangle, and the answer is the binomial coefficient "n choose k".

The base cases come from the edges of the table. With length 0 the only string is the empty one, which has zero ones, so dp[0][0] = 1. For any length i, exactly one string has no ones, the all-zeros string, so dp[i][0] = 1. Every entry with j > i stays 0, because a string cannot have more ones than characters.

Step by step

Build the table. dp := makeMatrix(n+1, k+1) uses the provided helper, which returns a 2D slice of n + 1 rows and k + 1 columns filled with zeros.
Set dp[0][0] = 1, the empty string. All the other values grow from this one.
Loop over lengths: i from 1 up to and including n. Row 0 is already complete.
Set dp[i][0] = 1. The inner loop starts at j = 1 and never touches column 0, so it is set here.
Loop over the number of ones: j from 1 up to and including k.
Add the two cases: dp[i][j] = dp[i-1][j] + dp[i-1][j-1].
Return dp[n][k].

The solution in Go

func countBinaryStrings(n, k int) int {
    dp := makeMatrix(n+1, k+1)
    dp[0][0] = 1
    for i := 1; i <= n; i++ {
        dp[i][0] = 1
        for j := 1; j <= k; j++ {
            dp[i][j] = dp[i-1][j] + dp[i-1][j-1]
        }
    }
    return dp[n][k]
}

The Go details worth a closer look:

Shared parameter type. In func countBinaryStrings(n, k int), the type int applies to both names. It is shorthand for n int, k int.
Why a helper builds the table. Go has no single expression for a 2D slice of a given size. A [][]int is a slice whose elements are slices, so each row has to be created on its own, and makeMatrix(rows, columns) does that in a loop. Writing make([][]int, rows) alone would give rows nil slices, and assigning to dp[0][0] would panic.
Two-step indexing. dp[i][j] first picks the row slice dp[i], then the element j of it. Rows are separate slices, so a table could even have rows of different lengths; makeMatrix gives them all the same length.
Nested loops. The inner for is a statement inside the body of the outer one, and its variable j exists only there. The outer loop's i stays visible inside.
Size. The largest entry the lesson can ask for is for n = 30 and k = 15, which is 155117520, comfortably inside int.

Complexity

Time: O(n * k), one addition for each cell of the table. Space: O(n * k) for the table. Each row depends only on the one above it, so keeping two rows would cut the space to O(k).

Edge cases and common mistakes

k = 0. The inner loop never runs, and the answer is dp[n][0], which is 1: the all-zeros string.
k = n. The only string is all ones. The table gives 1 for n = 3, k = 3.
n = 0 and k = 0. The loop on i does not run and the function returns dp[0][0], which is 1.
Forgetting dp[i][0] = 1. Column 0 stays at 0 below the first row, and every count in the table that depends on it comes out too small. For n = 4 and k = 2 the function would return 0.
Table dimensions. A table made with n rows and k columns has no row n and no column k, and dp[n][k] panics with an index out of range error. It needs n + 1 and k + 1.
Wrong inner bound. A loop that runs j up to i instead of k may reach column numbers beyond the table when i > k.

Testing

n = 4, k = 2 gives 6.
n = 3, k = 0 gives 1.
n = 3, k = 3 gives 1.
n = 5, k = 1 gives 5.
n = 30, k = 15 gives 155117520.

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

Start learning free