Problem overview
The function countBinaryStrings(n, k) returns how many binary strings of length n contain exactly k ones, with every one sitting on an even position. Positions are counted from 0, so the even positions are 0, 2, 4 and so on. The odd positions must hold zeros.
For n = 6 and k = 2 the even positions are 0, 2 and 4. Choosing two of them for the ones gives three strings: 101000 (ones at 0 and 2), 100010 (ones at 0 and 4) and 001010 (ones at 2 and 4). The answer is 3. The notes promise 2 * k <= n <= 30, so the input is small.
Approach: build the string one character at a time
Listing every string of length 30 is out of the question, since there are over a billion of them. Instead, count strings by what is true about their prefix. Let dp[i][j] be the number of strings of length i that contain j ones and respect the rule so far.
A string of length i + 1 is a string of length i with one more character at position i. There are only two choices for that character:
- A
0is always allowed. It leaves the number of ones unchanged, so every string counted indp[i][j]contributes todp[i+1][j]. - A
1is allowed only wheniis even. It raises the count by one, so every string indp[i][j]contributes todp[i+1][j+1], as long asj + 1does not passk.
Each string of length i + 1 comes from exactly one shorter string plus its last character, so nothing is counted twice and nothing is missed. Row 0 is the starting point: the empty string, with zero ones, is one way, so dp[0][0] = 1.
For n = 6 and k = 2 the table, one row per length, looks like this:
length 0: [1 0 0]
length 1: [1 1 0]
length 2: [1 1 0]
length 3: [1 2 1]
length 4: [1 2 1]
length 5: [1 3 3]
length 6: [1 3 3]
The columns are the counts of ones, 0 to 2. The bottom-right cell is the answer, 3. Notice that a row is copied unchanged whenever the position just added is odd (rows 2, 4 and 6): only a zero can go there.
Step by step
- Build the table. It needs
n + 1rows, for lengths 0 ton, andk + 1columns, for 0 tokones. The lesson providesmakeMatrixto allocate it; every cell starts at 0 because Go zeroes new slices. - Seed the empty string with
dp[0][0] = 1. - Loop over the positions
ifrom 0 ton - 1. Each pass decides the character at positioniand fills rowi + 1from rowi. - Loop over the counts of ones
jfrom 0 tok, inclusive, because the table hask + 1columns. - Place a zero by adding
dp[i][j]intodp[i+1][j]. No condition is needed. - Guard the one. The condition is
ieven andj < k. The second part also keepsj + 1inside the row. - Place the one by adding
dp[i][j]intodp[i+1][j+1]. - Return
dp[n][k]: full length, exactlykones.
The solution in Go
func countBinaryStrings(n, k int) int {
dp := makeMatrix(n+1, k+1)
dp[0][0] = 1
for i := 0; i < n; i++ {
for j := 0; j <= k; j++ {
dp[i+1][j] += dp[i][j]
if i%2 == 0 && j < k {
dp[i+1][j+1] += dp[i][j]
}
}
}
return dp[n][k]
}
Go details worth a closer look:
func countBinaryStrings(n, k int)declares two parameters that share the typeint.+=on a slice element works like on any variable. Since every cell starts at 0, the first write into a cell effectively sets it, and later writes accumulate. That is how a cell such asdp[3][1]collects contributions from two different cells in the row above.i%2 == 0is the even test. For the non-negative values ofiused here, the remainder is 0 or 1. (For a negative number, Go's%takes the sign of the dividend, so-3 % 2is-1, which is a reason to prefer comparing with 0 rather than testing for 1.)&&short-circuits: ifiis odd, the right side is never evaluated. In this loop the order doesn't change the result, because neither side has side effects or can panic.- The row index is safe.
dp[i+1]exists for everyiup ton - 1because there aren + 1rows, anddp[i+1][j+1]exists because the guard keepsj + 1 <= k. Without thej < kcheck, Go would stop the program with an "index out of range" panic atj = k.
Complexity
The two loops run n times and k + 1 times, and each pass does a constant amount of work, so the time is O(n * k). The table holds (n + 1) * (k + 1) integers, so the space is O(n * k) as well. Because row i + 1 depends only on row i, two rows would be enough if memory mattered.
Counts stay far below the limit of Go's 64-bit int for n up to 30: the largest possible answer is a binomial coefficient over at most 15 positions.
Edge cases and common mistakes
k = 0. Only the all-zero string qualifies, so the answer is 1. The table has a single column, and the guardj < knever lets a one in.- Counting positions from 1. The lesson's even positions start at 0. Testing
(i+1)%2 == 0would allow ones only on the second, fourth and later characters, and the example would give a different answer. - Looping
jup tok - 1. The cells in columnkmust still pass their strings forward through the zero rule, or strings that already have all their ones would be lost. - Using
=instead of+=. Two different earlier states can lead into the same cell, so the second write would erase the first.
Testing
Try countBinaryStrings(1, 0), which is 1 (the string 0), and countBinaryStrings(4, 2), which is 1 (only 1010). A useful cross-check: the even positions of a length-n string number (n + 1) / 2, and the answer is the number of ways to choose k of them. For n = 6 that is three positions, and choosing two gives 3.