Start learning free

LESSON 319 OF 348 · DYNAMIC PROGRAMMING

Binary Strings With K Ones in Kotlin: A 2D DP Table

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

Example:

Input: N = 4, K = 2
Output: 6
Explanation: [
    "1100",
    "1010",
    "1001",
    "0110",
    "0101",
    "0011"
]
Notes: K <= N <= 30
STEP 1 OF 7
    Ctrl + Enter to check

    KOTLIN · DYNAMIC PROGRAMMING

    Binary Strings With K Ones in Kotlin, explained

    Problem overview

    The function countBinaryStrings receives two non-negative Int values, n and k, with k <= n <= 30. It returns how many binary strings of length n contain exactly k ones. Only the count is needed.

    For n = 4 and k = 2, the strings are 1100, 1010, 1001, 0110, 0101 and 0011, so the answer is 6.

    Approach: look at the last character

    Two numbers define a subproblem here, the length and the number of ones, so the table has two dimensions. Let dp[i][j] be the number of binary strings of length i with exactly j ones.

    Take such a string and look at its last character.

    • If it is 0, the first i - 1 characters hold all j ones. There are dp[i - 1][j] such strings.
    • If it is 1, the first i - 1 characters hold j - 1 ones. There are dp[i - 1][j - 1] such strings.

    Every string falls into exactly one group, so dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]. This is the rule of Pascal's triangle, and dp[n][k] is the binomial coefficient "n choose k": the number of ways to pick which k of the n positions hold the ones.

    The base cases come from the edges. The empty string is the only string of length 0, and it has zero ones, so dp[0][0] = 1. For any length, the single string with no ones is all zeros, so dp[i][0] = 1.

    For n = 4 and k = 2, the table fills like this, with one row per length and one column per number of ones:

            j=0  j=1  j=2
i=0      1    0    0
i=1      1    1    0
i=2      1    2    1
i=3      1    3    3
i=4      1    4    6

    The entry in row 3, column 2 is 3: the strings 011, 101 and 110. It comes from row 2 as dp[2][2] + dp[2][1], which is 1 + 2. The one string in dp[2][2], 11, gets a 0 appended and becomes 110. The two strings in dp[2][1], 01 and 10, get a 1 appended and become 011 and 101. The bottom-right entry, 6, is the answer.

    The table also shows a limit. Entries such as dp[1][2] are 0, because a string of length 1 can't hold two ones. The formula produces that on its own: dp[1][2] is dp[0][2] + dp[0][1], and both are 0. So no special handling is needed for counts that are too large for the length.

    Step by step

    1. Create the table. dp is an array of n + 1 rows, each an IntArray of k + 1 zeros, so dp[i][j] exists for every length and every count of ones up to k.
    2. Set dp[0][0] = 1, the empty string. Every other entry is built from this one.
    3. Loop i over 1..n, filling one string length at a time.
    4. Set dp[i][0] = 1 for each row. The inner loop starts at j = 1 and never touches column 0, so it must be set here.
    5. Loop j over 1..k inside, to compute every count of ones for this length.
    6. Add the two cases: dp[i - 1][j] for a last character 0, and dp[i - 1][j - 1] for a last character 1.
    7. 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 1..n) {
            dp[i][0] = 1
            for (j in 1..k) {
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]
            }
        }
        return dp[n][k]
    }
}

    The Kotlin details worth a closer look:

    • A 2D table is an array of arrays. Array(n + 1) { IntArray(k + 1) } calls the lambda once for each of the n + 1 rows, and each call creates a separate row. Because every row is its own array, changing one entry never affects another row.
    • Zero by default. IntArray(k + 1) starts filled with zeros. That is why entries the loops never write, such as dp[0][j] for j > 0, are correctly 0: no string of length 0 has any ones.
    • Two sets of brackets. dp[i][j] first picks the row i, which is an IntArray, and then picks element j of that row. Unlike a C-style grid, there is no dp[i, j] form for arrays of arrays in Kotlin.
    • Inclusive ranges. 1..n and 1..k include their upper ends. Using until would stop one short. When k is 0, the inner range 1..0 is empty and the function returns the all-zeros count, 1.
    • Int is enough. The largest answer in the allowed range is for n = 30 and k = 15: 155,117,520, which fits in 32 bits.

    Complexity

    Time: O(n * k). Each of the n * k inner steps does one addition.

    Space: O(n * k). The table has (n + 1) * (k + 1) entries. Row i only reads row i - 1, so two rows would be enough.

    Edge cases and common mistakes

    • k = 0. countBinaryStrings(3, 0) is 1: only 000.
    • k = n. countBinaryStrings(3, 3) is 1: only 111.
    • n = 0. With k = 0 the loops never run and the function returns dp[0][0], which is 1.
    • Forgetting dp[i][0] = 1. Column 0 would stay 0, and then every other entry in the table would be too small.
    • Wrong table size. The table needs n + 1 rows and k + 1 columns. Sizes of n and k make dp[n][k] out of range.
    • Reading dp[i - 1][j - 1] at j = 0. That index would be -1. The inner loop starts at 1 to avoid it.

    Testing

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