LESSON 339 OF 414 · DYNAMIC PROGRAMMING

Binary Strings of Given Length in Scala: A DP Table

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 Scala, explained

Problem overview

The method countBinaryStrings receives an Int n and returns how many binary strings of length n exist. A binary string uses only the characters 0 and 1, and any combination is allowed. For n = 3 there are 8 of them: 000, 001, 010, 011, 100, 101, 110 and 111. The statement guarantees n is at most 30.

The lesson asks for the count, not for the strings themselves. Listing them would take time proportional to their number, which doubles with every extra character. Counting them can be done with a short loop.

Approach: extend every shorter string in two ways

Take any binary string of length i. Removing its last character leaves a binary string of length i - 1. In the other direction, each string of length i - 1 can be extended by appending 0 or by appending 1, and the two results are different strings. Every string of length i comes from exactly one string of length i - 1 and one choice of last character, so

count(i) = 2 * count(i - 1)

This is a small dynamic programming problem: the answer for length i is computed from the answer for the length before it. The base case is length 1, where the only strings are 0 and 1, so the count is 2. From there, 4, 8, 16 and so on follow. The closed form is 2 to the power n. The table is still worth writing, because the same pattern, a table filled in increasing order, solves harder counting problems, and this one makes the recurrence visible.

Step by step

Create the table. dp is an Array[Int] of size n + 1, so that index n exists. Entry i will hold the number of binary strings of length i. A new Array[Int] starts with all zeros.
Set the base case. dp(1) = 2, because a string of length 1 is either "0" or "1".
Loop over the longer lengths. for (i <- 2 to n) visits 2, 3, ..., n. The range 2 to n includes n, and every entry is computed after the one before it.
Apply the recurrence. dp(i) = dp(i - 1) * 2: each shorter string can be extended by a 0 or by a 1.
Return dp(n), which holds the count for the full length.

The solution in Scala

class Solution {
    def countBinaryStrings(n: Int): Int = {
        val dp = new Array[Int](n + 1)
        dp(1) = 2
        for (i <- 2 to n) {
            dp(i) = dp(i - 1) * 2
        }
        return dp(n)
    }
}

The Scala details worth a closer look:

Creating the array. new Array[Int](n + 1) makes an array of that size with every element set to 0. Its size is fixed from then on.
val fixes the name, not the elements. dp is a val, yet dp(i) = ... still works, because it changes an element of the array that dp refers to.
Round brackets for elements. Scala reads and writes array elements with dp(i), not dp[i]. The assignment dp(1) = 2 is shorthand for a call to the array's update method.
to includes its end, until excludes it. 2 to n ends at n. If n is 1, the range 2 to 1 is empty and the loop body never runs, which is correct, since dp(1) is already set.
Int is 32 bits. The largest value here, for n = 30, is 1,073,741,824, which fits. One more doubling would give 2,147,483,648, which is beyond the largest Int and wraps to -2,147,483,648 without any error. That is why the statement stops at 30. For larger lengths, a Long would be needed.

Complexity

Time: O(n). The loop runs at most n - 1 times and each pass does one multiplication.

Space: O(n). The table has n + 1 entries. Only the previous entry is ever read, so a single running variable would reduce the space to O(1), and 1 << n gives the answer directly.

Edge cases and common mistakes

n = 1. The loop body is skipped and the method returns dp(1), which is 2.
n = 0. The statement allows a non-negative n, and the one string of length 0 is the empty string, so the count should be 1. This solution creates an array with a single entry and then writes to dp(1), which doesn't exist, so it throws an ArrayIndexOutOfBoundsException. Setting dp(0) = 1 as the base case and starting the loop at 1 would cover it.
Array too small. Creating dp with size n instead of n + 1 makes dp(n) an invalid index.
Using until. 2 until n stops before n, so dp(n) stays 0.
Wrong base case. Starting with dp(1) = 1 halves every result.
Using ^ for powers. In Scala, ^ is bitwise exclusive or, not exponentiation, so 2 ^ 3 is 1. Use 1 << n or math.pow for powers of two.

Testing

n = 1 gives 2.
n = 2 gives 4.
n = 3 gives 8.
n = 10 gives 1024.
n = 30 gives 1073741824.

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

Start learning free