LESSON 345 OF 415 · DYNAMIC PROGRAMMING

Binary Strings With K Ones On Even Positions 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 exactly K ones placed only on even positions

Example:

Input: N = 6, K = 2
Output: 3
Explanation: [
    "101000",
    "100010",
    "001010"
]

Notes: 2 * K <= N <= 30

STEP 1 OF 8

Guided

Ctrl + Enter to check

SWIFT · DYNAMIC PROGRAMMING

Binary Strings With K Ones On Even Positions in Swift, explained

Problem overview

The method countBinaryStrings(_ n: Int, _ k: Int) counts binary strings of length n that contain exactly k ones, where every one sits on an even position. Positions start at 0, so the even positions are 0, 2, 4 and so on. Odd positions must hold a 0.

For n = 6 and k = 2 the answer is 3: 101000, 100010 and 001010. The ones are always at positions among 0, 2 and 4. The notes guarantee 2 * K <= N <= 30.

Approach: decide one position at a time

The table dp[i][j] counts the strings of length i that contain j ones and obey the rule. This lesson fills the table "forward": each cell hands its count to the cells it can grow into when the next character is chosen.

At position i there are two choices for the next character:

A 0 is always allowed. It keeps the number of ones the same, so dp[i][j] contributes to dp[i + 1][j].
A 1 is allowed only if i is even and fewer than k ones have been used. It raises the count by one, so dp[i][j] contributes to dp[i + 1][j + 1].

Because the table starts at zero and cells only receive additions, the order is simple: finish row i completely before using it to fill row i + 1. The loop over i guarantees that.

A quick check of the idea: only the even positions can hold ones, and there are (n + 1) / 2 of them, rounded down by integer division. The answer is the number of ways to choose k of them. For n = 6 that is choosing 2 of 3 positions, which is 3. The table computes the same number without needing that formula.

Step by step

Create the table as a var with n + 1 rows and k + 1 columns of zeros.
Seed it with dp[0][0] = 1: one empty string, zero ones.
Loop over positions i from 0 to n - 1. Each pass decides the character at position i and fills row i + 1. The last pass fills row n.
Loop over the one-counts j from 0 to k, so every reachable state passes its count forward.
Place a 0. Add dp[i][j] to dp[i + 1][j], with no condition.
Guard the 1. The branch runs only when i is even and j < k.
Place a 1. Add dp[i][j] to dp[i + 1][j + 1].
Return dp[n][k]: full length, exactly k ones.

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][j] += dp[i][j]
                if i % 2 == 0 && j < k {
                    dp[i + 1][j + 1] += dp[i][j]
                }
            }
        }
        return dp[n][k]
    }
}

Swift details worth knowing:

+= on a nested subscript. dp[i + 1][j] += dp[i][j] reads and writes the inner array element in place. It works because dp is a var.
Two range operators. 0..<n stops before n, which is right for positions, because the last position is n - 1. 0...k includes k, which is right for counts, because the table has columns 0 through k. For n = 0, the range 0..<0 is empty and the loop is skipped. A range with a lower bound above its upper bound would stop the program, but neither range here can have one when n and k are non-negative.
Short-circuit &&. j < k is checked only when i % 2 == 0 holds, and either way it must be true before the code touches column j + 1. This keeps the index inside the k + 1 columns. Swift arrays check bounds and crash on an invalid index instead of reading other memory.
Remainder. i % 2 == 0 is true for even non-negative i, which is all this loop produces.

Watching the table fill

Take n = 4 and k = 1. Row 0 is [1, 0].

Position 0 (even). From dp[0][0] = 1, a 0 gives dp[1][0] = 1 and a 1 gives dp[1][1] = 1. Row 1 is [1, 1].
Position 1 (odd). Only zeros can be placed. Row 2 is a copy of row 1: [1, 1].
Position 2 (even). The zero transition copies row 2 into row 3, giving [1, 1]. The one transition adds dp[2][0] = 1 to dp[3][1], so row 3 is [1, 2]. The cell dp[2][1] is not extended because j = k.
Position 3 (odd). Row 4 is a copy of row 3: [1, 2].

The answer is dp[4][1] = 2: the strings 1000 and 0010. The one-count cap shows up too: a cell with j = k can still receive zeros, but it never passes a 1 on, so no string ever ends up with more than k ones.

Complexity

Time: O(n * k). There are n positions and k + 1 counts, and each cell does a constant amount of work.

Space: O(n * k). The table has (n + 1) * (k + 1) cells. Each row depends only on the one before it, so two rows would be enough.

Edge cases and common mistakes

Counting positions from 1. The statement's example shows ones at positions 0 and 2 when positions start at 0. Using i % 2 == 1 by mistake would allow ones only at positions 1, 3 and 5, and the answer for n = 5, k = 3 would be 0 instead of 1.
Dropping the j < k guard. For j = k the code would write to column k + 1, which does not exist, and the program would crash.
Putting the zero transition inside the if. Odd positions would then pass nothing forward, and almost every count would be 0.
k = 0. The answer is 1, the all-zeros string: the 1-branch never runs.
Odd n. With n = 5 the even positions are 0, 2 and 4, so k = 3 gives 1.

Testing

n = 6, k = 2 gives 3.
n = 5, k = 3 gives 1.
n = 4, k = 0 gives 1.
n = 1, k = 1 gives 1.
n = 30, k = 15 gives 1.

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

Start learning free