LESSON 318 OF 348 · DYNAMIC PROGRAMMING

Binary Strings Without Consecutive Ones in Kotlin: Fibonacci DP

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

Guided

Ctrl + Enter to check

Binary Strings Without Consecutive Ones in Kotlin, explained

Problem overview

The function countBinaryStrings receives a non-negative Int named n and returns how many binary strings of length n contain no two 1 characters next to each other. Only the count is needed. The statement keeps n at 30 or below.

For n = 3, of the eight possible strings, 011, 110 and 111 are ruled out. The five valid ones are 000, 001, 010, 100 and 101, so the answer is 5.

Approach: look at how a valid string ends

Generating every string and filtering would take time proportional to 2 to the power n. Instead, split the valid strings of length i by their last character.

Ends in 0. The rest of the string, the first i - 1 characters, can be any valid string of length i - 1. Adding a 0 can never create two consecutive ones. That is dp[i - 1] strings.
Ends in 1. The character before it must be 0, otherwise two ones would touch. So the string ends in 01, and the first i - 2 characters can be any valid string of length i - 2. That is dp[i - 2] strings.

Every valid string falls into exactly one of these groups, so dp[i] = dp[i - 1] + dp[i - 2]. This is the Fibonacci recurrence.

The recurrence reaches back two steps, so it needs two base cases. For length 0 there is one string, the empty one. For length 1 there are two, "0" and "1", and neither contains two consecutive ones. After that, dp[2] = 3 (00, 01, 10), dp[3] = 5 and dp[4] = 8.

Step by step

Create dp as an IntArray of size n + 1, so each index holds the count for that length. It starts with zeros.
Store the base cases: dp[0] = 1 and dp[1] = 2, so the loop has two values to build from.
Loop i over 2..n, since each longer count builds on the two shorter ones.
Set dp[i] to the sum of the two previous entries.
Return dp[n], the last entry of the array.

The solution in Kotlin

class Solution {
    fun countBinaryStrings(n: Int): Int {
        val dp = IntArray(n + 1)
        dp[0] = 1
        dp[1] = 2
        for (i in 2..n) {
            dp[i] = dp[i - 1] + dp[i - 2]
        }
        return dp[n]
    }
}

The Kotlin details worth a closer look:

Zero-filled arrays. IntArray(n + 1) starts with every element 0, and val only fixes the reference, so the entries can still be assigned.
Ranges. 2..n includes n. When n is 1, the range 2..1 is empty and the loop body never runs, so the answer is dp[1].
Size of the answer. For n = 30 the result is 2,178,309, far below the 32-bit Int limit of 2,147,483,647, so there is no overflow in the allowed range.

Complexity

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

Space: O(n). The table has n + 1 entries. Each step reads only the last two, so two variables would reduce this to O(1).

Edge cases and common mistakes

n = 1. Returns 2, since both single characters are valid.
n = 0. The empty string is valid, so the answer should be 1. This code throws ArrayIndexOutOfBoundsException on it, because the array has one entry and dp[1] = 2 is out of range. An if (n == 0) return 1 guard at the top would fix it.
Counting only strings that end in 0. Dropping the dp[i - 2] term loses every string that ends in 01.
Wrong second base case. If dp[1] were set to 1, every later value would be too small.
Forbidding a leading 1. The rule is about two adjacent ones only. A string such as 101 is valid.

Testing

n = 1 gives 2.
n = 2 gives 3.
n = 3 gives 5.
n = 4 gives 8.
n = 30 gives 2178309.

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

Start learning free