LESSON 343 OF 415 · DYNAMIC PROGRAMMING

Binary Strings Without Consecutive Ones in Swift: A dp Array

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

SWIFT · DYNAMIC PROGRAMMING

Binary Strings Without Consecutive Ones in Swift, explained

Problem overview

The method countBinaryStrings receives a length n and returns how many strings of length n made of the characters 0 and 1 have no two 1s next to each other. For n = 3 the valid strings are 000, 001, 010, 100 and 101, so the answer is 5. The other three, 011, 110 and 111, each contain 11. The notes limit n to 30.

Only the count is returned. Generating and filtering all 2^n strings would also work for small n, but it grows exponentially, while a table gives the count in a few steps.

Approach: look at how a valid string ends

Let dp[i] be the number of valid strings of length i. Look at the end of such a string. It can't end in 11, so there are only two cases:

It ends in 0. Whatever comes before is any valid string of length i - 1, because a trailing 0 can't create a pair of ones. That gives dp[i - 1] strings.
It ends in 1. Then the character before must be 0, so the string ends in 01, and the part before that is any valid string of length i - 2. That gives dp[i - 2] strings.

The cases don't overlap, since they differ in the last character, and together they cover everything. So:

dp[i] = dp[i - 1] + dp[i - 2]

The base cases are dp[0] = 1, the empty string, and dp[1] = 2, the strings 0 and 1, neither of which can have two ones. Then dp[2] = 3 (00, 01, 10), dp[3] = 5, dp[4] = 8. These are Fibonacci numbers.

Step by step

Create the table: a var array dp of n + 1 zeros, with [Int](repeating: 0, count: n + 1). The size makes index n exist.
Set both base cases on one line, separated by a semicolon: dp[0] = 1; dp[1] = 2. The loop needs two earlier values to build from.
Loop over the lengths with i in 2..<(n + 1). The upper bound is excluded, so i reaches n. For n = 1 the range 2..<2 is empty and the loop doesn't run.
Add the two previous entries: dp[i] = dp[i - 1] + dp[i - 2].
Return dp[n], the last entry.

The solution in Swift

class Solution {
    func countBinaryStrings(_ n: Int) -> Int {
        var dp = [Int](repeating: 0, count: n + 1)
        dp[0] = 1; dp[1] = 2
        for i in 2..<(n + 1) {
            dp[i] = dp[i - 1] + dp[i - 2]
        }
        return dp[n]
    }
}

Swift details worth knowing:

Semicolons. Swift doesn't need semicolons at the end of lines, but they let two statements share a line, as in dp[0] = 1; dp[1] = 2.
Half-open range. 2..<(n + 1) excludes the end. The closed form 2...n would crash when n is 1, because a range whose lower bound is above its upper bound is invalid.
Integer size. The answer for n = 30 is 2178309, a tiny fraction of what a 64-bit Int holds. Swift stops the program on overflow rather than wrapping, but that can't happen within the limit.

Complexity

Time: O(n), one addition per length.

Space: O(n), for the table. Each entry needs only the two before it, so two variables would reduce it to O(1).

Edge cases and common mistakes

n = 1. The loop doesn't run and the answer is dp[1], which is 2.
n = 2. The answer is 3: 00, 01 and 10.
n = 0. The mathematical answer is 1, but the line dp[1] = 2 is out of range when the table has a single entry, so this solution crashes. The lesson's tests use lengths of at least 1; to support 0, return 1 before creating the table.
Using dp[i - 1] * 2. That counts all binary strings and includes ones with 11.
Wrong base case for dp[0]. If it is 0, the table is off from dp[2] on: dp[2] would be 2 instead of 3.

Testing

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

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

Start learning free