Start learning free

LESSON 343 OF 414 · DYNAMIC PROGRAMMING

Binary Strings With K Ones in Scala: 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

    SCALA · DYNAMIC PROGRAMMING

    Binary Strings With K Ones in Scala, explained

    Problem overview

    The method countBinaryStrings(n, k) returns how many binary strings of length n contain exactly k ones. The notes promise k <= n <= 30.

    For n = 4 and k = 2 the strings are 1100, 1010, 1001, 0110, 0101 and 0011, so the answer is 6. Listing the strings would work for tiny inputs, but there are 2^30 strings of length 30, which is more than a billion. The method has to count them without generating them.

    Approach: build longer strings from shorter ones

    Let dp(i)(j) be the number of binary strings of length i with exactly j ones. Look at the last character of such a string:

    • If it is 0, the first i - 1 characters hold all j ones. There are dp(i - 1)(j) of those.
    • If it is 1, the first i - 1 characters hold j - 1 ones. There are dp(i - 1)(j - 1) of those.

    Every string falls into exactly one of the two groups, so dp(i)(j) = dp(i - 1)(j) + dp(i - 1)(j - 1). This is the rule that builds Pascal's triangle: dp(n)(k) is the binomial coefficient "n choose k", the number of ways to pick which k of the n positions hold a one.

    The table needs starting values. The empty string is the only string of length 0 and has no ones, so dp(0)(0) = 1. A string of any length with no ones must be all zeros, so dp(i)(0) = 1.

    For k = 2 the table fills in like this. Each row lists the counts for 0, 1 and 2 ones:

    length 0:  1  0  0
length 1:  1  1  0
length 2:  1  2  1
length 3:  1  3  3
length 4:  1  4  6

    The 6 in the last row is dp(3)(2) + dp(3)(1), which is 3 + 3, and it matches the six strings listed above. The 3 in row 3 is dp(2)(2) + dp(2)(1), which is 1 + 2.

    Step by step

    1. Create the table with Array.ofDim[Int](n + 1, k + 1). It has a row for each length from 0 to n and a column for each count of ones from 0 to k. Every cell starts at 0.
    2. Set dp(0)(0) to 1. Every other value is built on this one.
    3. Loop over the lengths with 1 to n. The to range includes n, which is what the table needs, since the answer sits in row n.
    4. Set dp(i)(0) to 1 at the start of each row. The inner loop begins at j = 1 and never writes column 0, so this assignment is required.
    5. Loop over the counts of ones with 1 to k.
    6. Apply the rule: add the "last character is 0" count to the "last character is 1" count.
    7. Return dp(n)(k).

    The order matters. Row i reads only row i - 1, and the outer loop finishes each row before it starts the next, so every value is final when it is read.

    The solution in Scala

    class Solution {

    def countBinaryStrings(n: Int, k: Int): Int = {
        val dp = Array.ofDim[Int](n + 1, k + 1)
        dp(0)(0) = 1
        for (i <- 1 to n) {
            dp(i)(0) = 1
            for (j <- 1 to k) {
                dp(i)(j) = dp(i - 1)(j) + dp(i - 1)(j - 1)
            }
        }
        return dp(n)(k)
    }
}

    Some Scala details in this code:

    • Array.ofDim[Int](n + 1, k + 1) allocates all the rows at once, and the type in square brackets is the element type. Int cells start at 0, so there is no initialisation loop. The result is an Array[Array[Int]].
    • Arrays are indexed with parentheses. Scala writes dp(i)(j), not dp[i][j], because an array lookup is a method call, apply. The assignment dp(i)(j) = ... calls update in the same way.
    • val fixes the reference, not the contents. dp always names the same array, but its cells can be changed.
    • 1 to n against 1 until n. to includes the upper bound and until excludes it. Using until here would leave row n empty and the method would return 0.
    • for (i <- 1 to n) is a loop over a range. When the range is empty, as in 1 to 0, the body never runs.
    • return works, but Scala code usually ends with the value as the last expression: writing just dp(n)(k) returns the same result.

    Complexity

    Time: O(n * k). The table has (n + 1) * (k + 1) cells, and each one takes a constant amount of work.

    Space: O(n * k). The table is the only extra memory. Since row i uses only row i - 1, two rows would be enough if memory mattered, but with n <= 30 it doesn't.

    Edge cases and common mistakes

    • Forgetting dp(i)(0) = 1. Column 0 would stay at 0 for every row except row 0, and every count in the table would come out too small. For n = 4, k = 2 the answer would be 0 instead of 6.
    • k = 0. The table has a single column and the inner loop never runs. For n = 5 the method returns 1, the all-zeros string.
    • k = n. There is exactly one string, all ones. countBinaryStrings(3, 3) returns 1.
    • n = 0. The outer loop doesn't run and dp(0)(0) is 1, so countBinaryStrings(0, 0) returns 1: the empty string.
    • Overflow. Int is 32 bits in Scala and overflow wraps silently. Here the largest value the notes allow is countBinaryStrings(30, 15), which is 155117520 and fits comfortably.
    • Off-by-one table size. Rows and columns are counted from 0, so the table needs n + 1 and k + 1 of them. With n and k the final lookup would be out of bounds.

    Testing

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