Start learning free

LESSON 315 OF 348 · DYNAMIC PROGRAMMING

Binary Strings of Given Length in Kotlin: A First DP Table

Practice O(n) Read the full explanation

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
    Ctrl + Enter to check

    KOTLIN · DYNAMIC PROGRAMMING

    Binary Strings Of Given Length in Kotlin, explained

    Problem overview

    The function countBinaryStrings receives a non-negative Int named n and returns how many binary strings of length n exist, that is, strings made only of the characters 0 and 1. Only the count is needed, not the strings themselves. The statement keeps n at 30 or below.

    For n = 3 the eight strings are 000, 001, 010, 011, 100, 101, 110 and 111, so the answer is 8.

    Approach: each string extends a shorter one

    Listing and counting the strings would take time proportional to the answer itself, which is over a billion for n = 30. Counting from smaller cases is much cheaper.

    Every binary string of length i is a binary string of length i - 1 followed by one more bit, and that last bit can be 0 or 1. So each shorter string leads to exactly two longer ones, and no longer string is produced twice. That gives the recurrence dp[i] = 2 * dp[i - 1], where dp[i] is the number of binary strings of length i.

    A recurrence needs a starting point. With length 1 the only strings are "0" and "1", so dp[1] = 2. From there the table is filled in increasing order of length, which guarantees that dp[i - 1] is ready when dp[i] needs it. This is a small example of dynamic programming: store the answers to smaller subproblems and build the larger ones from them.

    Step by step

    1. Create the table. dp is an IntArray of size n + 1, so that index n exists. It starts filled with zeros.
    2. Set the base case dp[1] = 2.
    3. Loop i over 2..n, so every longer length is computed after the one before it.
    4. Double the previous entry to get dp[i].
    5. Return dp[n], which now holds the count for the full length.

    The solution in Kotlin

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

    The Kotlin details worth a closer look:

    • IntArray(n + 1) creates an array of primitive ints, all set to 0. val dp fixes the variable, not the elements, so dp[i] = ... is allowed.
    • Inclusive ranges. 2..n includes both ends. When n is 1, the range 2..1 is empty and the loop body never runs, so the answer is dp[1], which is 2.
    • 32-bit Int. The answer is 2 to the power n. For n = 30 that is 1,073,741,824, which fits. One more doubling would not: 2 * 1073741824 wraps to -2,147,483,648, because Kotlin's Int overflow is silent. That is why the statement stops at 30.

    Complexity

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

    Space: O(n). The table has n + 1 entries. Only the previous entry is ever read, so a single running variable would reduce this to O(1), and the closed form is simply 2 to the power n. The table makes the recurrence easier to see, which is the point of the lesson.

    Edge cases and common mistakes

    • n = 1. The loop is skipped and the function returns 2.
    • n = 0. The statement allows it, and the answer should be 1, since the empty string is the only string of length 0. This code fails on it, though: the array has a single entry, so dp[1] = 2 throws ArrayIndexOutOfBoundsException. Adding if (n == 0) return 1 at the top handles it.
    • Table too small. Creating IntArray(n) instead of IntArray(n + 1) makes dp[n] fail for every input.
    • Wrong loop start. Starting at 1 would read dp[0], which is 0 here, and overwrite the base case with 0.
    • Going past 30. From n = 31 the result no longer fits in an Int. A Long table would extend the range to n = 62.

    Testing

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