LESSON 344 OF 414 · DYNAMIC PROGRAMMING

Binary Strings With K Ones on Even Positions in Rust

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

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

Problem overview

The function count_binary_strings takes two numbers, n and k, both usize. It returns how many binary strings of length n contain exactly k ones, with every one sitting on an even position. Positions are counted from 0, so position 0 is the first character.

For n = 6 and k = 2 the even positions are 0, 2 and 4. The ones must go on two of those three, which gives 101000, 100010 and 001010. The answer is 3. The odd positions are always 0.

Approach: build the string one character at a time

Counting by listing every string would take 2^n steps, and n can reach 30. Dynamic programming avoids that by counting prefixes. Let dp[i][j] be the number of strings of length i that hold exactly j ones, all on even positions. Every string of length i + 1 is a string of length i with one more character, so row i + 1 can be computed from row i:

Appending a 0 is always allowed and leaves the number of ones unchanged: dp[i][j] flows into dp[i + 1][j].
Appending a 1 is allowed only when the new character lands on an even position, that is, when i (the position of the new character) is even. It raises the count of ones: dp[i][j] flows into dp[i + 1][j + 1].

The table starts from the empty string, dp[0][0] = 1, and the answer is dp[n][k]. For n = 4 and k = 1 the single one may sit at position 0 or 2, so the answer is 2: 1000 and 0010.

Step by step

Create the table. There are n + 1 rows, one for each length from 0 to n, and k + 1 columns, one for each count of ones from 0 to k. Every cell starts at 0. The table is declared with let mut because the cells change.
Seed the empty string. There is exactly one string of length 0, and it has zero ones, so dp[0][0] becomes 1. Every other count grows from this single starting point.
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 number of ones j from 0 to k, inclusive, so every reachable state passes its ways forward.
Place a 0. Add dp[i][j] to dp[i + 1][j]. This needs no condition.
Check whether a 1 is allowed. It must be an even position, and j must still be below k, because a count above k is never useful and would not fit in the table.
Place the 1. Add dp[i][j] to dp[i + 1][j + 1].
Return the cell dp[n][k]: strings of full length with exactly k ones.

The solution in Rust

impl Solution {
    fn count_binary_strings(n: usize, k: usize) -> i32 {
        let mut dp = vec![vec![0; k + 1]; n + 1];
        dp[0][0] = 1;
        for i in 0..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];
                }
            }
        }
        dp[n][k]
    }
}

The Rust details worth knowing:

vec![value; count]. The macro repeats a value by cloning it. The inner vec![0; k + 1] is a row, and the outer macro clones that row n + 1 times, so each row is a separate vector. Changing one cell never affects another row.
The cell type is inferred. The literal 0 has no type of its own. The last expression, dp[n][k], must be an i32 to match the return type, so the compiler makes every cell an i32.
The tail expression. dp[n][k] has no semicolon and no return, so it is the function's value. With a semicolon the function would return () and fail to compile.
Inclusive and exclusive ranges. 0..n stops at n - 1, which is what the position loop needs. 0..=k includes k, which the columns need.
Indexing with usize. n, k, i and j are all usize, so they index the vectors directly, with no casts. An index outside the vector panics, which is why the j < k guard matters before writing to column j + 1.
i % 2 == 0. The remainder test finds even positions. Because i counts from 0, the first character counts as even.

Complexity

Time: O(n * k). The two loops visit every pair of position and count once, and each visit does a constant amount of work.

Space: O(n * k). The table holds (n + 1) * (k + 1) numbers. Since row i + 1 only reads row i, two rows would be enough if memory mattered, but at n = 30 it doesn't.

Edge cases and common mistakes

Too many ones. With n = 4 and k = 3 there are only two even positions, so the answer is 0. The table handles this without a special case.
Zero ones. k = 0 gives 1 for every n: the string of all zeros.
Every even position used. n = 5 and k = 3 gives 1, the string 10101.
Counting positions from 1. If you test i % 2 == 1, the ones go on odd 0-based positions and the counts are wrong. For n = 6, k = 2 the answer would still be 3 by coincidence, but n = 5, k = 3 would give 0.
Dropping the j < k guard. Writing to dp[i + 1][k + 1] is outside the row and panics.
Looping j up to k - 1. Column k then never passes its ways forward, and the zeros of the remaining positions are lost.

Testing

n = 6, k = 2 gives 3.
n = 4, k = 0 gives 1.
n = 5, k = 3 gives 1.
n = 4, k = 3 gives 0.
n = 30, k = 7 gives 6435, the number of ways to choose 7 of the 15 even positions.

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

Start learning free