Start learning free

LESSON 342 OF 414 · DYNAMIC PROGRAMMING

Binary Strings Without Consecutive Ones in Scala: DP

Practice O(n) Read the full explanation

Given a non-negative integer N return the number of binary strings of length N without 2 consecutive ones

Example:

Input: N = 3
Output: 5
Explanation: [
    "000",
    "001",
    "010",
    "100",
    "101",
]
Notes: N <= 30
STEP 1 OF 5
    Ctrl + Enter to check

    SCALA · DYNAMIC PROGRAMMING

    Binary Strings Without Consecutive Ones in Scala, explained

    Problem overview

    The method countBinaryStrings receives an Int n and returns how many binary strings of length n do not contain two 1 characters in a row. For n = 3 the answer is 5: 000, 001, 010, 100 and 101. The other three strings of length 3, 011, 110 and 111, each contain 11. The statement guarantees n is at most 30.

    There are 2^n binary strings of length n, and checking each of them would take far too long for n = 30. The lesson counts them with a recurrence instead.

    Approach: look at how a valid string ends

    Take a valid string of length i. Its last character is either 0 or 1:

    • If it ends in 0, the first i - 1 characters can be any valid string of length i - 1. A trailing 0 never creates a pair of ones.
    • If it ends in 1, the character before it must be 0, otherwise the string ends in 11. So it ends in 01, and the first i - 2 characters can be any valid string of length i - 2.

    Those two cases cover every valid string exactly once, so

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

    This is the Fibonacci recurrence. It needs two starting values. There is one valid string of length 0, the empty string, and two of length 1, 0 and 1, since neither can hold two ones. Then count(2) is 3 (00, 01, 10), count(3) is 5, count(4) is 8, and so on.

    Each value depends on the two before it, so the table is filled from the smallest length upward, which makes sure both values are ready when they are needed.

    Step by step

    1. Create the table. dp is a new Array[Int] of size n + 1, declared with val. Entry i will hold the count for length i. A new array starts filled with zeros.
    2. Store the base cases. dp(0) = 1 and dp(1) = 2. Neither string of length 1 can contain two ones.
    3. Loop over the longer lengths. for (i <- 2 to n) runs from 2 to n inclusive.
    4. Apply the recurrence. dp(i) = dp(i - 1) + dp(i - 2): strings ending in 0 plus strings ending in 01.
    5. Return dp(n), the last entry of the table.

    The solution in Scala

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

    The Scala details worth a closer look:

    • Arrays are fixed-size and zero-filled. new Array[Int](n + 1) reserves n + 1 slots, all 0. The size can't change afterwards, so it has to include index n.
    • val fixes the name, not the elements. dp is a val, but dp(i) = ... still changes an element of the array.
    • Round brackets index arrays. Scala writes dp(i - 1), not dp[i - 1]. Square brackets are for type parameters, as in Array[Int].
    • to and until. 2 to n includes n, while 2 until n stops one short. For n = 1 the range 2 to 1 is empty, so the loop doesn't run and the method returns dp(1).
    • Int overflow. The counts grow like Fibonacci numbers. For n = 30 the result is 2,178,309, which is small. An Int holds values up to about 2.1 billion, and the table would stay correct up to n = 44. For n = 45 the sum wraps around silently and the method returns a negative number, -1323752223. The limit of 30 in the statement keeps the answers well in range.

    Complexity

    Time: O(n). The loop runs n - 1 times and does one addition each time.

    Space: O(n). The table has n + 1 entries. Each entry needs only the previous two, so two running variables would use O(1) space.

    Edge cases and common mistakes

    • n = 1. The answer is 2, from the base case. The loop doesn't run.
    • n = 0. The statement allows a non-negative n, and the correct count is 1 for the empty string. This solution sets dp(1) on an array that has only index 0, so for n = 0 it throws an ArrayIndexOutOfBoundsException. Guarding the second base case with if (n >= 1) would fix it.
    • Using the wrong base case. Setting dp(0) = 0 shifts every result. With dp(0) = 1 and dp(1) = 2, the third entry is 3, as the strings 00, 01 and 10 show.
    • Adding dp(i - 1) twice. Treating a trailing 1 like a trailing 0 counts strings that end in 11. A trailing 1 needs a 0 before it.
    • Allowing 11 in the prefix. The prefix before a trailing 01 has length i - 2 and is itself valid, which is why the term is dp(i - 2).
    • Table too small. Creating dp with size n leaves no room for dp(n).

    Testing

    • n = 1 gives 2.
    • n = 2 gives 3.
    • n = 3 gives 5.
    • n = 4 gives 8.
    • n = 10 gives 144.
    • n = 30 gives 2178309.
    Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free