LESSON 346 OF 415 · FREE CODING INTERVIEW QUESTIONS

Binary Strings with At Most K Consecutive Ones in Swift: DP

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

SWIFT · FREE CODING INTERVIEW QUESTIONS

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

Problem overview

The method countBinaryStrings takes 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 notes give k <= n <= 30.

For n = 4 and k = 2 there are 16 binary strings of length 4. Three of them have a run of three or more ones: 0111, 1110 and 1111. The other 13 are valid, so the answer is 13.

Approach: build strings one character at a time

Listing every string and checking each one takes O(2^n * n) work, which is hopeless at n = 30, where there are more than a billion strings. We only need a count, and the validity of a string depends on very little: the length so far and how many ones the string currently ends with.

So define dp[i][j] as the number of valid strings of length i that end in exactly j consecutive ones. The number j never exceeds k in a valid string. A string of length i can be extended by one more character in two ways:

Append a 0. The run of ones ends, so the new string ends in 0 ones. Every string counted in dp[i][j], for any j, contributes to dp[i + 1][0].
Append a 1. The run grows from j to j + 1. That is allowed only when j < k, and then dp[i][j] contributes to dp[i + 1][j + 1].

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

For n = 4 and k = 2 the rows, with columns for j = 0, 1, 2, are:

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

The last row sums to 7 + 4 + 2 = 13.

Step by step

Create dp as a grid of zeros with n + 1 rows (lengths 0 through n) and k + 1 columns (trailing ones 0 through k). It is a var, because the loops write into it.
Seed the base case. The empty string is the one valid string of length 0, and it ends in zero ones, so dp[0][0] = 1.
Loop over lengths with i from 0 to n - 1. Each pass pushes the counts of row i forward into row i + 1, so the last row to read from is n - 1.
Loop over j from 0 to k. A valid string can end in any number of ones in that range. The closed range 0...k includes k.
Handle appending a 0. Add dp[i][j] into dp[i + 1][0] with +=. Several values of j feed the same cell, so the addition has to accumulate.
Handle appending a 1. Guard it with if j < k, and add dp[i][j] into dp[i + 1][j + 1]. Without the guard, j + 1 could reach k + 1, which is both an invalid string and a column that does not exist.
Declare result after the loops, starting at 0, so that it is not reset on every pass.
Sum the last row. A valid string of length n can end in 0 to k ones, so add every dp[n][j].
Return result.

The solution in Swift

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

Swift details worth knowing:

Building the grid. [Int](repeating: 0, count: k + 1) makes one row of zeros, and the outer [[Int]](repeating: ..., count: n + 1) makes n + 1 copies of it. Arrays are value types, so each row is independent: writing to dp[1][0] does not change dp[2][0].
Ranges. 0..<n stops before n, and 0...k includes k. Using the wrong one is an easy off-by-one here.
A closed range needs k >= 0. 0...k with a negative k stops the program, but the task says k is non-negative.
Compound assignment on nested subscripts. dp[i + 1][0] += dp[i][j] reads and writes one cell, which is fine because the two sides are different cells.
No overflow. The counts never exceed 2^30 for n <= 30, far below the 64-bit limit of Int. Swift would stop the program on overflow rather than wrap, but it can't happen here.

Calling it:

let solution = Solution()
print(solution.countBinaryStrings(4, 2))
print(solution.countBinaryStrings(3, 1))
print(solution.countBinaryStrings(5, 0))
print(solution.countBinaryStrings(30, 30))

Complexity

Time: O(n * k). The nested loops fill each of the n transitions across k + 1 columns with constant work, and the final sum adds O(k). Since k <= n, that is at most O(n²).

Space: O(n * k). The table has (n + 1) * (k + 1) cells. Each row depends only on the previous one, so two rows would be enough, but the full table is easier to read.

Edge cases and common mistakes

K equals 0. No ones are allowed, so only the all-zeros string is valid: countBinaryStrings(5, 0) returns 1. The table has a single column and the if j < k branch never runs.
K equals N. Every string is valid, so the answer is 2^n: countBinaryStrings(30, 30) returns 1,073,741,824.
N equals 0. The loops over lengths do not run, and the sum of row 0 is just the empty string: the result is 1.
Missing the base case. Without dp[0][0] = 1 the whole table stays zero.
Using = instead of +=. Each cell in column 0 receives a contribution from every j, and plain assignment would keep only the last one.
Dropping the j < k guard. It would index column k + 1 and crash.
Summing the wrong row. The answer is row n, not any earlier row.

Testing

n = 4, k = 2 gives 13.
n = 3, k = 1 gives 5: 000, 001, 010, 100 and 101.
n = 5, k = 0 gives 1.
n = 1, k = 1 gives 2.
n = 3, k = 3 gives 8.

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

Start learning free