LESSON 309 OF 338 · DYNAMIC PROGRAMMING

Binary Strings Without Consecutive Ones in Go: Fibonacci DP

Given a non-negative integer N return the number of binary strings of length N without 2 consecutive ones

Example:

Input: N = 3
Output: 5
Explanation: [
    "000",
    "001",
    "010",
    "100",
    "101",
]

Notes: N <= 30

STEP 1 OF 5

Guided

Ctrl + Enter to check

Binary Strings Without Consecutive Ones in Go, explained

Problem overview

The function countBinaryStrings takes an int n and returns how many binary strings of length n do not contain two 1 characters next to each other. For n = 3 the answer is 5: 000, 001, 010, 100 and 101. The other three strings of length 3, 011, 110 and 111, are excluded. The lesson's notes say n is at most 30.

Approach: look at how a valid string ends

Counting all strings and removing the bad ones is awkward. It is easier to build the count from shorter valid strings by looking at the end of a valid string of length i. It ends in one of two ways:

It ends in 0. What comes before is any valid string of length i - 1, because a 0 can't create a pair of ones. That gives dp[i-1] strings.
It ends in 1. The character before that 1 must be 0, since 11 is not allowed. So the string ends in 01, and what comes before that is any valid string of length i - 2. That gives dp[i-2] strings.

The two groups do not overlap and together cover every valid string, so dp[i] = dp[i-1] + dp[i-2]. This is the Fibonacci recurrence with different starting values. The bases are dp[0] = 1, the empty string, and dp[1] = 2, the strings 0 and 1, neither of which contains a pair of ones. The table then runs 1, 2, 3, 5, 8, 13 and so on, and the entry for length 3 is 5, as in the example.

Step by step

Create the table with make([]int, n+1). Index i will hold the count for length i.
Set both base cases in one statement: dp[0], dp[1] = 1, 2. The loop needs two earlier values to build from.
Loop with i from 2 while i <= n. Each count depends on the two before it.
Add the two previous entries: dp[i] = dp[i-1] + dp[i-2].
Return dp[n].

The solution in Go

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

The Go details worth a closer look:

Tuple assignment. dp[0], dp[1] = 1, 2 assigns both elements in one statement. Go evaluates the right side first and then assigns. The same form swaps two values without a temporary variable: a, b = b, a.
Slices are checked at run time. Indexing a slice outside its length panics. That matters here for n = 0, as explained below.
Zero values. make([]int, n+1) fills the table with zeros, so entries from 2 on are overwritten by the loop and no cell is left uninitialised.
Size. The largest answer for n = 30 is 2178309, well inside the range of int.

Complexity

Time: O(n). Space: O(n) for the table. Each step needs only the last two entries, so two variables would bring the space down to O(1).

Edge cases and common mistakes

n = 1. The loop does not run and the answer is dp[1], which is 2.
n = 2. The valid strings are 00, 01 and 10, and the function returns 3. Only 11 is excluded.
n = 0. The empty string is valid, so 1 is the right answer, but this solution does not produce it. The slice has length 1, and dp[1] = 2 panics with an index out of range error. The lesson's notes do not promise that 0 is tested; if you need to handle it, return 1 first when n == 0.
Using 1 as the base for length 1. The strings 0 and 1 are both valid, so the count is 2, not 1.
Counting the "ends in 1" group as dp[i-1]. Appending a 1 to a valid string is only allowed if that string ends in 0. The correct count for the group is dp[i-2], strings that end in 01.
Confusing it with the plain count. Without the restriction the answer would be 2^n. For n = 3 that is 8, against 5 here.

Testing

n = 1 gives 2.
n = 2 gives 3.
n = 3 gives 5.
n = 4 gives 8.
n = 30 gives 2178309.

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

Start learning free