Problem overview
The function countBinaryStrings takes an int n and returns how many binary strings of length n exist: strings made only of the characters 0 and 1. For n = 3 the answer is 8, and the eight strings are 000, 001, 010, 011, 100, 101, 110 and 111. The lesson's notes say n is at most 30.
Approach: extend shorter strings by one bit
Listing all the strings and counting them would work for small n, but their number grows fast. Counting is easier than listing: every string of length i is a string of length i - 1 followed by one more bit. That bit is either 0 or 1, so each shorter string extends in exactly two ways, and different shorter strings (or different bits) never produce the same longer string. The count of length i is therefore twice the count of length i - 1.
This is the pattern of dynamic programming: define a table where dp[i] is the answer for size i, fill in a starting value, and compute each later entry from the earlier ones. Here the starting value is dp[1] = 2, since the only strings of length 1 are "0" and "1".
Step by step
- Create the table.
dp := make([]int, n+1)makes a slice ofn + 1zeros, so the indices 0 tonexist anddp[i]can hold the count for lengthi. - Set the base case:
dp[1] = 2. - Loop from 2 to
ninclusive. Usingi <= nmakes the loop reachnitself. Filling in increasing order guarantees thatdp[i-1]is ready whendp[i]needs it. - Double the previous entry:
dp[i] = dp[i-1] * 2. - Return
dp[n], the count for the full length.
The solution in Go
func countBinaryStrings(n int) int {
dp := make([]int, n+1)
dp[1] = 2
for i := 2; i <= n; i++ {
dp[i] = dp[i-1] * 2
}
return dp[n]
}
The Go details worth a closer look:
make([]int, n+1). It builds a slice with lengthn + 1and every element set to the zero value ofint, which is 0. The table could not be an array here, because an array's size must be a constant known at compile time.- The only loop is
for. Go has nowhile. The three-part forminit; condition; postworks as in C, without parentheses, and the braces are required. :=declares and infers.dp := make(...)declaresdpwith the slice type. Declaring a variable and never using it is a compile error in Go.- Room to grow.
intis 64 bits in Go 1.22 on 64-bit systems, so2^30, the largest answer, which is 1073741824, fits with a wide margin.
Because the answer is just 2 to the power n, a shortcut exists: 1 << n shifts a 1 left by n bits. The table makes the recurrence visible, which is the point of the exercise, and the same shape returns in the harder lessons that follow.
Complexity
Time: O(n), one loop with a constant amount of work per step. Space: O(n) for the table. Since each entry only reads the one before it, a single running variable would reduce the space to O(1).
Edge cases and common mistakes
n = 1. The loop does not run, and the function returnsdp[1], which is 2.n = 0. There is exactly one string of length 0, the empty string, so the mathematically right answer is 1. This solution does not handle it:dphas only index 0, and the assignmentdp[1] = 2panics with an index out of range error. The lesson's notes give no promise about 0, so if you need it, add an earlyif n == 0 { return 1 }or start the table atdp[0] = 1.- Making the table too small.
make([]int, n)has no indexn, and readingdp[n]panics. - Using
i < n. The loop stops one entry early anddp[n]is left at 0. - Adding instead of doubling.
dp[i-1] + 1grows linearly; every shorter string has two extensions, not one.
Testing
n = 1gives2.n = 3gives8.n = 10gives1024.n = 30gives1073741824.