LESSON 320 OF 348 · DYNAMIC PROGRAMMING

Binary Strings With K Ones on Even Positions in Kotlin: DP

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 placed only on even positions

Example:

Input: N = 6, K = 2
Output: 3
Explanation: [
    "101000",
    "100010",
    "001010"
]

Notes: 2 * K <= N <= 30

STEP 1 OF 8

Guided

Ctrl + Enter to check

KOTLIN · DYNAMIC PROGRAMMING

Binary Strings With K Ones On Even Positions in Kotlin, explained

Problem overview

The function countBinaryStrings(n, k) returns how many binary strings of length n contain exactly k ones, with every one standing on an even position. Positions are counted from 0, so the even positions are 0, 2, 4 and so on. Every odd position must hold a 0.

For n = 6 and k = 2 the answer is 3. The even positions are 0, 2 and 4, and the three ways to choose two of them give 101000, 100010 and 001010. The notes guarantee 2 * K <= N <= 30.

Approach: build the string one character at a time

Listing every binary string of length 30 is out of the question, since there are over a billion of them. Dynamic programming avoids that by counting instead of listing. Define dp[i][j] as the number of valid strings of length i that contain j ones. Every longer string is a shorter valid string plus one more character, so each row of the table comes from the row before it.

The new character goes at position i, because a string of length i fills positions 0 to i - 1. There are two choices:

A 0 is always allowed. The count of ones stays at j, so dp[i][j] flows into dp[i + 1][j].
A 1 is allowed only when i is even and we still need more ones. The count becomes j + 1, so dp[i][j] flows into dp[i + 1][j + 1].

The starting point is the empty string: one string of length 0 with zero ones. The answer is the cell for full length and exactly k ones, dp[n][k].

There is also a shortcut worth noticing. The odd positions are fixed at 0, so the only real decision is which k of the even positions get a 1. A string of length n has (n + 1) / 2 even positions (integer division), so the answer is the binomial coefficient "choose k of those". For n = 6 and k = 2 that is 3 choose 2, which is 3. The table computes the same numbers without needing a formula, and the same technique carries over to rules a formula can't capture.

Step by step

Create the table. It has n + 1 rows because lengths run from 0 to n, and k + 1 columns because the number of ones runs from 0 to k.
Seed the empty string. Set dp[0][0] to 1. Everything else starts at 0 and is filled from this one cell.
Loop over positions i from 0 to n - 1. Each pass decides the character at position i and fills row i + 1.
Loop over the counts j from 0 to k inclusive. Every reachable state has to pass its ways forward, and k itself is a valid column.
Place a 0. Add dp[i][j] to dp[i + 1][j] with no condition.
Guard the 1. Check that i is even and j < k. The second test also keeps j + 1 inside the table.
Place a 1. Add dp[i][j] to dp[i + 1][j + 1].
Return dp[n][k].

The solution in Kotlin

class Solution {
    fun countBinaryStrings(n: Int, k: Int): Int {
        val dp = Array(n + 1) { IntArray(k + 1) }
        dp[0][0] = 1
        for (i in 0 until n) {
            for (j in 0..k) {
                dp[i + 1][j] += dp[i][j]
                if (i % 2 == 0 && j < k) {
                    dp[i + 1][j + 1] += dp[i][j]
                }
            }
        }
        return dp[n][k]
    }
}

The Kotlin details worth a closer look:

Building a 2D table. Array(n + 1) { IntArray(k + 1) } calls the lambda once per row, so every row is its own IntArray. An IntArray starts filled with zeros, which is what the table needs.
val fixes the name, not the contents. dp always refers to the same array of rows, but the cells can still change, so dp[0][0] = 1 compiles.
Ranges. 0 until n stops at n - 1, while 0..k includes k. Mixing them up is the classic off-by-one error: with 0 until k the column k would never pass its count forward.
+= on an array element. dp[i + 1][j] += dp[i][j] reads the cell, adds, and stores the result back. Several earlier states can feed one cell, so the update has to add rather than assign.
Int is enough. With N <= 30 there are at most 15 even positions, so the largest answer is 6435, the number of ways to pick 7 of 15 positions.

Complexity

Time: O(n * k). The two loops visit each of the n positions and each of the k + 1 counts once, and every visit does a constant amount of work.

Space: O(n * k). The table has (n + 1) * (k + 1) cells. Since row i + 1 only reads row i, two rows would suffice, but the full table is easier to follow.

Edge cases and common mistakes

k = 0. Only the all-zero string qualifies, so countBinaryStrings(4, 0) returns 1.
Every even position holds a one. countBinaryStrings(5, 3) returns 1: positions 0, 2 and 4 are the only candidates, and all three are used.
Too many ones. countBinaryStrings(3, 2) returns 1, since positions 0 and 2 are both even. Asking for more ones than there are even positions gives 0, because no path reaches that cell.
Counting positions from 1. In the example, 101000 has its ones at positions 0 and 2. If you treat position 1 as the first even position, the table counts a different set of strings.
Dropping the j < k test. At j = k the write to dp[i + 1][j + 1] goes past the last column and throws ArrayIndexOutOfBoundsException.
Using i + 1 in the parity test. The character being placed sits at position i, so i % 2 == 0 is the right test.

Testing

n = 6, k = 2 gives 3.
n = 4, k = 0 gives 1.
n = 5, k = 3 gives 1.
n = 30, k = 5 gives 3003.
n = 30, k = 15 gives 1.

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

Start learning free