Start learning free

LESSON 343 OF 414 · DYNAMIC PROGRAMMING

Binary Strings With K Ones in Rust: 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

    RUST · DYNAMIC PROGRAMMING

    Binary Strings With K Ones in Rust, explained

    Problem overview

    The function count_binary_strings takes a length n and a number of ones k, and returns how many binary strings of length n contain exactly k ones. The statement guarantees K ≤ N ≤ 30.

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

    Approach: a table indexed by length and number of ones

    Two numbers describe a subproblem: how long the string is and how many ones it must hold. Let dp[i][j] be the number of binary strings of length i with exactly j ones. The table needs rows 0 to n and columns 0 to k.

    To fill an entry, look at the last character of such a string. If it is 0, the first i - 1 characters hold all j ones, which gives dp[i - 1][j] strings. If it is 1, the first i - 1 characters hold the other j - 1 ones, which gives dp[i - 1][j - 1] strings. The cases are separate and cover everything:

    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]

    The base cases are dp[0][0] = 1, the empty string with no ones, and dp[i][0] = 1 for every i, because the only string without a one is all zeros. The recurrence is the one that builds Pascal's triangle, so dp[n][k] is the binomial coefficient "n choose k". For n = 4 and k = 2 the entries come out as follows:

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

    Each row is cut off at column 2, because k is 2, and the answer is the 6 at the end of the last row.

    The entry dp[4][2] shows both cases at work. Strings of length 4 with two ones that end in 0 are the three strings of length 3 with two ones, 110, 101 and 011, followed by a 0: that is 1100, 1010 and 0110. Strings that end in 1 are the three strings of length 3 with one one, 100, 010 and 001, followed by a 1: 1001, 0101 and 0011. Together they are the six strings from the example, and 3 + 3 matches dp[3][2] + dp[3][1].

    Step by step

    1. Create dp as n + 1 rows of k + 1 zeros with vec![vec![0; k + 1]; n + 1], declared let mut. Both n and k are already usize, the type Rust uses for sizes and indices.
    2. Set dp[0][0] = 1. Everything else is built from this entry.
    3. Loop over the lengths with i in 1..=n. Row 0 is already complete.
    4. Set dp[i][0] = 1 inside the loop. The inner loop starts at column 1 and never touches column 0, so it is set here.
    5. Loop over the counts of ones with j in 1..=k.
    6. Add the two cases: dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]. Both entries are in the previous row, which is complete by then.
    7. Return dp[n][k] as the final expression.

    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 1..=n {
            dp[i][0] = 1;
            for j in 1..=k {
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
            }
        }
        dp[n][k]
    }
}

    The Rust details worth a closer look:

    • Nested vec!. vec![x; count] makes count copies of x. With x being a whole Vec, each row is a separate clone, so changing one row never affects another. The element type is inferred as i32 from the return type.
    • Two-step indexing. dp[i][j] is (dp[i])[j]: the first index picks a row and the second picks a column inside it.
    • Unsigned subtraction. i - 1 and j - 1 are usize subtractions. They are safe because both loops start at 1. A loop starting at 0 would wrap in an optimized build, or panic in a debug build, and the following index would then be out of range.
    • Overflow. The largest value allowed is the binomial coefficient of 30 and 15, which is 155,117,520. It fits in an i32.
    • Inclusive ranges. 1..=n and 1..=k include their last values. With 1..k the last column would never be computed.

    Complexity

    Time: O(n * k). The table has (n + 1) * (k + 1) entries, and each takes constant time.

    Space: O(n * k). The whole table is kept. Each row only needs the one before it, so keeping two rows would reduce this to O(k).

    Edge cases and common mistakes

    • K = 0. Returns 1: the all-zeros string. The inner loop doesn't run, and dp[n][0] is already 1. For n = 5 and k = 0, the result is 1.
    • K = N. Returns 1, the all-ones string.
    • N = 0 and K = 0. Returns 1, the empty string. The outer loop doesn't run, and dp[0][0] is 1.
    • Forgetting dp[i][0] = 1. Column 0 stays 0 below the first row, and then every entry that depends on it is wrong. For n = 2 and k = 1 the function would return 1 instead of 2.
    • Using too small a table. A table with n rows or k columns has no row n or column k, and dp[n][k] panics with an index out of bounds.
    • Using the wrong previous entry. The "ends in 1" case uses dp[i - 1][j - 1], with one fewer one. Using dp[i - 1][j] twice would double the count of the "ends in 0" case.

    Testing

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