Start learning free

LESSON 339 OF 414 · DYNAMIC PROGRAMMING

Binary Strings of Given Length in Rust: A First DP Table

Practice O(n) Read the full explanation

Given a non-negative integer N return the number of binary strings of length N

Example:

Input: N = 3
Output: 8
Explanation: [
    "000",
    "001",
    "010",
    "011",
    "100",
    "101",
    "110",
    "111"
]
Notes: N <= 30
STEP 1 OF 5
    Ctrl + Enter to check

    RUST · DYNAMIC PROGRAMMING

    Binary Strings Of Given Length in Rust, explained

    Problem overview

    The function count_binary_strings takes a length n and returns how many binary strings of exactly that length exist, where a binary string is made only of the characters 0 and 1. The statement limits N to 30.

    For n = 3 the strings are 000, 001, 010, 011, 100, 101, 110 and 111, so the answer is 8.

    Approach: build each length from the previous one

    Listing the strings would work for tiny inputs, but the count grows fast, and counting is easier than listing. Let dp[i] be the number of binary strings of length i. Every string of length i is a string of length i - 1 followed by one more character, and that character is either 0 or 1. Each shorter string can therefore be extended in exactly two ways, and no two different extensions give the same result. So:

    dp[i] = 2 * dp[i - 1]

    With the base case dp[1] = 2 (the strings "0" and "1"), the table runs 2, 4, 8, 16 and so on. This is dynamic programming in its simplest form: a table of answers for small sizes, and a rule that gets each entry from earlier ones. The closed form is 2^n, but the table shows the pattern that harder problems in this chapter build on.

    Step by step

    1. Create dp with vec![0; n + 1], declared let mut because the entries will change. Index i stores the count for length i, so the vector needs n + 1 slots for index n to exist. The element type is inferred as i32 from the function's return type.
    2. Set the base case dp[1] = 2.
    3. Loop over the lengths from 2 to n with 2..=n. The = makes the range include n. Filling in increasing order guarantees that dp[i - 1] is ready when it is needed.
    4. Double the previous entry: dp[i] = dp[i - 1] * 2.
    5. Return dp[n] as the final expression, without a semicolon.

    The solution in Rust

    impl Solution {
    fn count_binary_strings(n: usize) -> i32 {
        let mut dp = vec![0; n + 1];
        dp[1] = 2;
        for i in 2..=n {
            dp[i] = dp[i - 1] * 2;
        }
        dp[n]
    }
}

    The Rust details worth a closer look:

    • n is a usize. Lengths and indices in Rust are usize, so n + 1 and dp[n] need no conversion. The result type is still i32.
    • Inclusive and exclusive ranges. 2..=n visits 2, 3, ..., n. Writing 2..n would stop at n - 1 and return the entry for the wrong length. When n is 1, 2..=1 is an empty range, so the loop doesn't run.
    • Indexing is checked. Reading or writing past the end of a vector panics instead of touching other memory.
    • Overflow. The count for length 30 is 1,073,741,824, which fits in an i32. Length 31 would need 2,147,483,648, one more than i32::MAX. In an optimized build the arithmetic wraps silently, and the function would return -2147483648. In a debug build it would panic instead. The limit N ≤ 30 keeps the code on the safe side.

    Complexity

    Time: O(n). The loop runs at most n - 1 times, with one multiplication each.

    Space: O(n). The table has n + 1 entries. Since each entry only needs the previous one, a single running variable would reduce this to O(1), but the table is the habit this lesson is building.

    Edge cases and common mistakes

    • N = 1. Returns 2 straight from the base case, and the loop is skipped.
    • N = 0. The empty string is the one string of length 0, so the true count is 1. This code doesn't handle it: dp has length 1, and dp[1] = 2 panics with "index out of bounds: the len is 1 but the index is 1". A version that sets dp[0] = 1 and starts the loop at 1 would cover it.
    • Exclusive range. 2..n leaves dp[n] at 0 for every n above 1.
    • Allocating only n entries. vec![0; n] has no index n, so the final dp[n] panics.
    • Adding instead of multiplying. dp[i - 1] + 2 would give 2, 4, 6, 8 and miss the doubling.

    Testing

    • n = 1 gives 2.
    • n = 3 gives 8.
    • n = 10 gives 1024.
    • n = 30 gives 1073741824.
    Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free