Start learning free

LESSON 344 OF 415 · DYNAMIC PROGRAMMING

Binary Strings With K Ones in Swift: Dynamic Programming

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

Example:

Input: N = 4, K = 2
Output: 6
Explanation: [
    "1100",
    "1010",
    "1001",
    "0110",
    "0101",
    "0011"
]
Notes: K <= N <= 30
STEP 1 OF 7
    Ctrl + Enter to check

    SWIFT · DYNAMIC PROGRAMMING

    Binary Strings With K Ones in Swift, explained

    Problem overview

    The method countBinaryStrings(_ n: Int, _ k: Int) returns how many binary strings of length n contain exactly k ones. A binary string is a sequence of 0 and 1 characters, and two strings are different if they differ at any position.

    For n = 4 and k = 2 the strings are 1100, 1010, 1001, 0110, 0101 and 0011, so the answer is 6. The notes guarantee K <= N <= 30.

    Approach: build longer strings from shorter ones

    Listing every string of length n and counting its ones takes 2^n steps, which is far too slow for n = 30. Dynamic programming avoids it by counting without listing.

    Let dp[i][j] be the number of strings of length i with exactly j ones. Take any such string and look at its last character:

    • If the last character is 0, the first i - 1 characters hold all j ones. There are dp[i - 1][j] such strings.
    • If the last character is 1, the first i - 1 characters hold j - 1 ones. There are dp[i - 1][j - 1] such strings.

    Every string falls into exactly one of those two groups, so dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]. Each cell depends only on two cells in the row above, so filling the table row by row works. This is Pascal's triangle: dp[n][k] is the binomial coefficient "n choose k".

    Step by step

    1. Create the table. It has n + 1 rows and k + 1 columns, all zeros, because lengths run from 0 to n and one-counts from 0 to k. It is a var since the loops write into it.
    2. Set dp[0][0] = 1. The empty string has length 0 and no ones, and it is the only such string. Every other count grows from this one.
    3. Loop over the lengths i from 1 to n. Row 0 is already complete.
    4. Set dp[i][0] = 1. With no ones allowed, the only string is all zeros. The inner loop starts at j = 1, so this column has to be set here. Without it, the formula would read zeros where it needs ones.
    5. Loop over the one-counts j from 1 to k.
    6. Apply the recurrence: add the count that ends in 0 to the count that ends in 1.
    7. Return dp[n][k], the cell for the full length and the full number of 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 1..<(n + 1) {
            dp[i][0] = 1
            for j in 1..<(k + 1) {
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]
            }
        }
        return dp[n][k]
    }
}

    Swift details worth knowing:

    • Nested repeating:count:. The inner call builds one row of k + 1 zeros, and the outer call copies it n + 1 times. Arrays are value types, so each row is an independent copy. Writing to dp[1][0] does not change dp[2][0].
    • Half-open ranges. 1..<(n + 1) excludes its upper bound, so i goes up to n. It is the same sequence as 1...n. An empty range such as 1..<1 is fine and the loop body simply never runs. A range whose lower bound is greater than its upper bound, such as 1..<0, stops the program with a run-time error.
    • var and value semantics. A let array cannot be changed, so a table that is filled in has to be a var.
    • Traps on overflow. Int is 64 bits and an overflowing addition crashes the program instead of wrapping. Here the largest value allowed by the notes is C(30, 15) = 155117520, far below the limit.

    Watching the table fill

    For n = 4 and k = 2 the table has 5 rows and 3 columns. Row 0 is [1, 0, 0]. After that, each row starts with 1, and each other cell is the cell above it plus the cell above and to the left:

    i=0: 1 0 0
i=1: 1 1 0
i=2: 1 2 1
i=3: 1 3 3
i=4: 1 4 6

    The bottom-right cell is 6, the answer. Read the cell in row 2, column 1 as "strings of length 2 with one 1": 01 and 10, so 2. The cell in row 4, column 1 is 4, one string for each position the single 1 can take. Because k is only 2, the table stops at column 2 and never computes the rest of Pascal's triangle.

    Complexity

    Time: O(n * k). The table has about n * k cells and each is computed with one addition.

    Space: O(n * k). The full table is stored. Row i only needs row i - 1, so keeping two rows would reduce this to O(k), but the table form is easier to read.

    Edge cases and common mistakes

    • k = 0. The answer is 1, the all-zeros string. The inner range 1..<1 is empty, and dp[n][0] was set to 1 by the outer loop.
    • k = n. The answer is 1, the all-ones string. For example n = 5, k = 5 returns 1.
    • n = 0. The loop does not run and the method returns dp[0][0], which is 1: the empty string.
    • Forgetting dp[i][0] = 1. Every cell in column 1 would be wrong, and the error spreads through the whole triangle.
    • Swapping the table's dimensions. Rows are lengths (n + 1 of them) and columns are one-counts (k + 1). Reversing them goes out of bounds when n and k differ.

    Testing

    • n = 4, k = 2 gives 6.
    • n = 3, k = 1 gives 3.
    • n = 5, k = 0 gives 1.
    • n = 5, k = 5 gives 1.
    • n = 30, k = 15 gives 155117520.
    Keep going with SwiftAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free