LESSON 340 OF 415 · DYNAMIC PROGRAMMING

Binary Strings of Given Length in Swift: Counting with a dp Array

Given a non-negative integer N return the number of binary strings of length N

Example:

Input: N = 3
Output: 8
Explanation: [
    "000",
    "001",
    "010",
    "011",
    "100",
    "101",
    "110",
    "111"
]

Notes: N <= 30

STEP 1 OF 5

Guided

Ctrl + Enter to check

Binary Strings Of Given Length in Swift, explained

Problem overview

The method countBinaryStrings receives a length n and returns how many strings of length n can be written using only the characters 0 and 1. For n = 3 there are eight: 000, 001, 010, 011, 100, 101, 110 and 111. The notes limit n to 30.

Only the count is requested, so the strings themselves never need to be built.

Approach: extend each shorter string in two ways

Every string of length i is a string of length i - 1 followed by one more bit. That last bit can be 0 or 1, so each shorter string produces exactly two longer ones, and no two shorter strings produce the same longer one. The count therefore doubles with each extra character:

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

This is a small dynamic programming table: dp[i] holds the answer for length i, and each entry is computed from the one before it. The base case is length 1, where only "0" and "1" exist, so dp[1] is 2. From there, dp[2] is 4, dp[3] is 8, and in general dp[n] is 2 to the power n. The table makes the recurrence visible; a single running variable, or a shift such as 1 << n, would give the same result.

Step by step

Create the table. Declare dp with var as [Int](repeating: 0, count: n + 1). The size n + 1 makes index n valid, and var is needed because the loop writes into it.
Set the base case: dp[1] = 2.
Loop over the lengths from 2 to n. The half-open range 2..<(n + 1) excludes its upper bound, so i takes the values 2 through n, and each length is computed after the one before it.
Double the previous entry: dp[i] = dp[i - 1] * 2.
Return dp[n].

The solution in Swift

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

Swift details worth knowing:

..< against .... 2..<(n + 1) excludes the end. When n is 1, the range is 2..<2, which is empty, and the loop body is skipped. The closed form 2...n would crash for n = 1, because a range whose lower bound is above its upper bound is invalid in Swift.
Integer size. Int is 64 bits here, so 2^30 is 1073741824 and fits easily. Arithmetic overflow in Swift stops the program instead of wrapping, and it would only matter near 2^63.
Array initialiser. [Int](repeating: 0, count: n + 1) builds an array of n + 1 zeros.

Complexity

Time: O(n). The loop runs n - 1 times with one multiplication each.

Space: O(n). The table has n + 1 entries. Since each entry depends only on the previous one, a single variable would reduce this 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 = 0. The table has only index 0, so the line dp[1] = 2 is out of range and the program crashes. The mathematical answer would be 1 (the empty string), but the lesson's tests use lengths of at least 1. If you need to support 0, return 1 before creating the table.
Table of size n. Then dp[n] doesn't exist. The table needs n + 1 entries.
Starting the loop at 1. It would overwrite the base case with dp[0] * 2, which is 0.

Testing

n = 1 gives 2.
n = 3 gives 8.
n = 30 gives 1073741824.

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

Start learning free