Start learning free

LESSON 342 OF 414 · DYNAMIC PROGRAMMING

Binary Strings Without Consecutive Ones in Rust: DP

Practice O(n) Read the full explanation

Given a non-negative integer N return the number of binary strings of length N without 2 consecutive ones

Example:

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

    RUST · DYNAMIC PROGRAMMING

    Binary Strings Without Consecutive Ones in Rust, explained

    Problem overview

    The function count_binary_strings takes a length n and returns how many binary strings of that length contain no two adjacent ones. The statement limits N to 30.

    For n = 3 there are 8 binary strings, and three of them contain "11": 011, 110 and 111. The other five are valid: 000, 001, 010, 100 and 101. The answer is 5.

    Approach: look at how a valid string can end

    Checking all 2^n strings one by one is too slow for N = 30, where there are more than a billion. Counting by structure is much faster.

    Let dp[i] be the number of valid strings of length i. Look at the last character of such a string:

    • If it is 0, the first i - 1 characters can be any valid string of length i - 1. A trailing zero can't create a pair of ones. That gives dp[i - 1] strings.
    • If it is 1, the character before it must be 0, or two ones would touch. So the string ends in "01", and the first i - 2 characters are any valid string of length i - 2. That gives dp[i - 2] strings.

    Those two cases don't overlap and cover every valid string, so:

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

    This is the Fibonacci recurrence. The base cases are dp[0] = 1 (the empty string) and dp[1] = 2 (the strings "0" and "1", neither of which can contain a pair). The table runs 1, 2, 3, 5, 8, 13. For length 2 the valid strings are 00, 01 and 10, which is the 3 in the table, and for length 3 the answer is 5, as in the example.

    Step by step

    1. Create dp with vec![0; n + 1], declared let mut. Entry i is the count for length i.
    2. Set the base cases: dp[0] = 1 and dp[1] = 2. The loop needs two earlier entries to start from.
    3. Loop over 2..=n. The inclusive range reaches n.
    4. Add the two cases: dp[i] = dp[i - 1] + dp[i - 2].
    5. Return dp[n] as the final expression.

    The solution in Rust

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

    The Rust details worth a closer look:

    • Inferred element type. vec![0; n + 1] has no annotation. The function returns dp[n] as an i32, so Rust infers that the elements are i32.
    • Why usize. The parameter n is a usize, the type for sizes and indices, so it serves as the loop bound and the index with no casts. A usize can't be negative, which is why i - 2 is safe here: i starts at 2, so the subtraction never goes below zero.
    • Ranges. 2..=n includes n. 2..n would stop one short.
    • Bounds checking. Writing to dp[1] when the vector is shorter than 2 panics at run time. See the edge cases below.
    • No overflow. dp[30] is 2,178,309, far below the largest i32.

    Complexity

    Time: O(n). The loop does one addition per length.

    Space: O(n). The table has n + 1 entries. Each entry depends on only the previous two, so two variables would be enough for O(1) space.

    Edge cases and common mistakes

    • N = 1. Returns 2: both "0" and "1" are valid, and the loop is skipped.
    • N = 2. Returns 3. Only "11" is excluded.
    • N = 0. The empty string is valid, so the count should be 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". The tests use positive lengths.
    • Using dp[0] = 0. The base case for the empty string must be 1. With 0, dp[2] would be 2, missing one of the three valid strings of length 2.
    • Counting only strings that end in "0". Leaving out the "01" case gives dp[i] = dp[i - 1], which would never grow past 2.

    Testing

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