LESSON 321 OF 348 · FREE CODING INTERVIEW QUESTIONS

Binary Strings with at Most K Consecutive Ones 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 at most K consecutive ones

Example:

Input: N = 4, K = 2
Output: 13
Explanation: [
    "0000",
    "0001",
    "0010",
    "0011",
    "0100",
    "0101",
    "0110",
    "1000",
    "1001",
    "1010",
    "1011",
    "1100",
    "1101",
]
"0111", "1110" and "1111" are not valid because they have more than 2 consecutive ones

Notes: K <= N <= 30

STEP 1 OF 9

Guided

Ctrl + Enter to check

KOTLIN · FREE CODING INTERVIEW QUESTIONS

Binary Strings With At Most K Consecutive Ones in Kotlin, explained

Problem overview

The function countBinaryStrings receives two non-negative integers, n and k, with k <= n <= 30. It returns how many binary strings of length n contain no run of more than k ones in a row. Only the count is needed, not the strings.

For n = 4 and k = 2 there are 16 binary strings in total. Three of them have a run of three or more ones: 0111, 1110 and 1111. The other 13 are valid, so the answer is 13.

Approach: count strings by how they end

The brute-force way is to generate all 2^n strings and check each one. With n = 30 that is over a billion strings, which is far too slow. Because only the number of strings matters, there is a faster way, based on one observation: whether a string can be extended depends only on how many ones it currently ends with.

So define dp[i][j] as the number of valid strings of length i that end in exactly j consecutive ones. A string can grow by one character in two ways:

Append a 0. The run of ones is broken, so the new string ends in 0 ones. This is allowed for every j.
Append a 1. A string ending in j ones now ends in j + 1 ones. This is allowed only when j < k, because a run of k + 1 ones would break the limit.

The table starts with the empty string: one valid string of length 0, ending in 0 ones, so dp[0][0] = 1. Every other string is built from it by appending characters. The answer is the sum of the last row, dp[n][0] through dp[n][k], because a valid string of length n may end in any number of ones from 0 to k.

For n = 4 and k = 2, the rows of the table (columns j = 0, 1, 2) are:

i=0: 1 0 0
i=1: 1 1 0
i=2: 2 1 1
i=3: 4 2 1
i=4: 7 4 2

The last row sums to 7 + 4 + 2 = 13.

Step by step

Create the table. dp has n + 1 rows (lengths 0 to n) and k + 1 columns (0 to k trailing ones). Kotlin fills it with zeros.
Record the empty string with dp[0][0] = 1.
Loop over the lengths i from 0 to n - 1. Each pass pushes the counts of length i forward into row i + 1, so the last row written is row n.
Loop over the trailing-ones counts j from 0 to k, including k.
Append a 0: add dp[i][j] to dp[i + 1][0]. It uses +=, because every j contributes to the same cell.
Append a 1: if j < k, add dp[i][j] to dp[i + 1][j + 1].
Sum the last row. Declare result as a var starting at 0, after the nested loops, and add dp[n][j] for each j from 0 to k.
Return result.

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][0] += dp[i][j]
                if (j < k) {
                    dp[i + 1][j + 1] += dp[i][j]
                }
            }
        }
        var result = 0
        for (j in 0..k) {
            result += dp[n][j]
        }
        return result
    }
}

The Kotlin details worth knowing:

Building the table. Array(n + 1) { IntArray(k + 1) } calls the lambda once per row, and each call creates a new IntArray of k + 1 zeros. Every row is a separate array. Repeating a single row object would make all rows share the same numbers.
Range bounds. 0 until n excludes n, while 0..k includes k. The two loops use them deliberately: i must stop at n - 1 because the body writes into row i + 1, while j must reach k because a string can end in exactly k ones.
+= on an array element. dp[i + 1][0] += dp[i][j] reads the cell, adds, and stores the result back. It is shorthand for dp[i + 1][0] = dp[i + 1][0] + dp[i][j].
val dp with changing contents. val stops dp from being pointed at a different table; it doesn't stop the numbers in it from changing.
Int is enough. It holds values up to 2147483647. For n = 30 the largest possible answer is 2^30 = 1073741824, reached when k = 30, so no sum overflows within the limits. Larger n would need Long.

Complexity

Time: O(n * k). The nested loops run n times k + 1 times, with constant work in each pass. The final sum adds O(k).

Space: O(n * k). The table has (n + 1) * (k + 1) cells. Row i + 1 depends only on row i, so two rows would be enough to cut the space to O(k). This lesson keeps the whole table, which makes the structure easier to see and check.

Edge cases and common mistakes

k = 0. No ones are allowed, so exactly one string qualifies, all zeros. countBinaryStrings(3, 0) returns 1.
k = n. Every string is valid, so the answer is 2^n. countBinaryStrings(3, 3) returns 8.
n = 0. The empty string is the only string, and the function returns 1.
k = 1. No two ones may touch. countBinaryStrings(4, 1) returns 8.
Using = instead of += for the appended 0. Each j would overwrite the previous contribution, and only the last would count.
Dropping the j < k guard. The code would write to dp[i + 1][k + 1], which is outside the row, and throw an ArrayIndexOutOfBoundsException.
Looping i up to n. The last pass would write into row n + 1, which doesn't exist.
Summing only dp[n][k]. That counts strings ending in exactly k ones, not all valid strings.

Testing

n = 4, k = 2 gives 13.
n = 4, k = 1 gives 8.
n = 3, k = 0 gives 1.
n = 3, k = 3 gives 8.
n = 1, k = 1 gives 2.
n = 5, k = 2 gives 24.

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

Start learning free