LESSON 312 OF 338 · FREE CODING INTERVIEW QUESTIONS

Binary Strings With At Most K Consecutive Ones in Go: Dynamic Programming

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 at most K consecutive ones

Example:

Input: N = 4, K = 2
Output: 13
Explanation: [
    "0000",
    "0001",
    "0010",
    "0011",
    "0100",
    "0101",
    "0110",
    "1000",
    "1001",
    "1010",
    "1011",
    "1100",
    "1101",
]
"0111", "1110" and "1111" are not valid because they have more than 2 consecutive ones

Notes: K <= N <= 30

STEP 1 OF 9

Guided

Ctrl + Enter to check

GO · FREE CODING INTERVIEW QUESTIONS

Binary Strings With At Most K Consecutive Ones in Go, explained

Problem overview

The function countBinaryStrings receives two non-negative integers, n and k, and returns how many binary strings of length n contain no run of more than k consecutive ones. The statement guarantees k <= n <= 30.

For n = 4 and k = 2, there are 16 binary strings of length 4. Three of them break the limit: 0111, 1110 and 1111 all contain three ones in a row. The other 13 are valid, so the answer is 13.

Approach

Generating every string and checking it is O(2^n) work, and with n up to 30 that is over a billion strings. The answer itself is a count, so a better idea is to count strings without ever building them.

A valid string can be built one character at a time. Whether a new character is allowed depends on a single fact about the string so far: how many ones it ends with. That makes the state small. Let dp[i][j] be the number of valid strings of length i that end in exactly j consecutive ones. From a string counted there you can append:

a 0, which is always allowed and resets the run, so the new string belongs to dp[i+1][0];
a 1, which extends the run to j + 1 and is allowed only while j < k, so the new string belongs to dp[i+1][j+1].

Every valid string of length i + 1 comes from exactly one valid string of length i by removing its last character, so no string is counted twice or missed. The answer is the sum of the last row, dp[n][0] through dp[n][k].

For n = 4, k = 2 the table looks like this, with one row per length and one column per trailing-ones count:

i=0  [1 0 0]
i=1  [1 1 0]
i=2  [2 1 1]
i=3  [4 2 1]
i=4  [7 4 2]    7 + 4 + 2 = 13

You can check a few cells by hand. In row 2, dp[2][0] is 2: the strings 00 and 10 end in a zero. dp[2][1] is 1 (01), and dp[2][2] is 1 (11). Row 3 then gets dp[3][0] = 2 + 1 + 1 = 4, because a zero can be appended to every string of length 2. Column 2 of row 3 is dp[2][1], which is 1: only a string ending in exactly one 1 can grow into one ending in two. A string ending in two ones can't take another 1, since that would be a run of three.

Step by step

Create the table dp with n + 1 rows (lengths 0 to n) and k + 1 columns (trailing ones 0 to k), filled with zeros. The lesson provides a makeMatrix(rows, columns) helper for this.
Seed the table: dp[0][0] = 1. The empty string is the one valid string of length 0, and it ends in zero ones.
Loop over lengths i from 0 to n - 1. The body writes into row i + 1, and the last row is n.
Loop over trailing-ones counts j from 0 to k inclusive.
Append a 0: add dp[i][j] to dp[i+1][0]. Several values of j feed this one cell, so it uses +=.
Append a 1 when allowed: if j < k, add dp[i][j] to dp[i+1][j+1].
Declare result := 0 after the loops.
Add up the last row: loop j from 0 to k and add every dp[n][j] to result.
Return result.

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][0] += dp[i][j]
            if j < k {
                dp[i+1][j+1] += dp[i][j]
            }
        }
    }
    result := 0
    for j := 0; j <= k; j++ {
        result += dp[n][j]
    }
    return result
}

The Go details worth a closer look:

Building a 2D slice. Go has no one-line constructor for a table of a given size. A [][]int is a slice of slices, and each row has to be allocated separately. A helper like this one does it:

func makeMatrix(rows, cols int) [][]int {
    m := make([][]int, rows)
    for i := range m {
        m[i] = make([]int, cols)
    }
    return m
}

Zero values. make([]int, cols) fills the row with zeros, which is why += works on cells that were never assigned.
Shared parameter type. n, k int declares both parameters as int.
Size. int is 64 bits here, and the largest possible answer is 2^30, which fits comfortably.
Index arithmetic. dp[i+1][j+1] is why the guard is j < k: at j == k the index k + 1 would be out of range, and Go stops the program with a panic instead of ignoring it.

Complexity

Time: O(n * k). The two nested loops run n times k + 1 times with constant work in each, and the final sum takes O(k). Space: O(n * k) for the table. Since row i + 1 depends only on row i, two rows would be enough, but the lesson keeps the whole table to make the idea easy to follow.

Edge cases and common mistakes

k = 0. No ones are allowed, so exactly one string qualifies: all zeros. countBinaryStrings(3, 0) returns 1. The table has a single column and the j < k branch never runs.
k = n. Every string is valid, so the answer is 2^n. countBinaryStrings(3, 3) returns 8.
n = 0. The only string is the empty one, and the answer is 1.
Looping j < k instead of j <= k. A string may end in exactly k ones, so column k must be processed and included in the final sum. Missing it undercounts.
Using = instead of += for dp[i+1][0]. Each j overwrites the previous contribution instead of adding to it.
Looping i up to n. The body writes to row i + 1, which doesn't exist for i == n, so the program panics.

Testing

countBinaryStrings(4, 2) gives 13.
countBinaryStrings(3, 1) gives 5: the strings with no two adjacent ones are 000, 001, 010, 100 and 101.
countBinaryStrings(3, 0) gives 1.
countBinaryStrings(3, 3) gives 8.
countBinaryStrings(0, 0) gives 1.

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

Start learning free