LESSON 345 OF 414 · FREE CODING INTERVIEW QUESTIONS

Binary Strings with At Most K Consecutive Ones in Rust: DP

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 at most K consecutive ones

Example:

Input: N = 4, K = 2
Output: 13
Explanation: [
    "0000",
    "0001",
    "0010",
    "0011",
    "0100",
    "0101",
    "0110",
    "1000",
    "1001",
    "1010",
    "1011",
    "1100",
    "1101",
]
"0111", "1110" and "1111" are not valid because they have more than 2 consecutive ones

Notes: K <= N <= 30

STEP 1 OF 9

Guided

Ctrl + Enter to check

RUST · FREE CODING INTERVIEW QUESTIONS

Binary Strings With At Most K Consecutive Ones in Rust, explained

Problem overview

The function count_binary_strings takes two non-negative integers, n and k, as usize. It returns how many binary strings of length n contain no run of more than k ones in a row. The note in the statement says k <= n <= 30.

For n = 4 and k = 2 there are 16 strings in total. Only 0111, 1110 and 1111 contain three ones in a row, so the answer is 13.

Approach: build strings one character at a time

Generating all 2^n strings and checking each is possible for small n, but with n = 30 that is over a billion strings. Counting is better than listing.

To decide whether a character can be appended to a valid string, you don't need the whole string. You only need to know how many ones it ends with. If it ends with j ones:

Appending 0 is always allowed, and the new string ends with 0 ones.
Appending 1 is allowed only if j < k, and the new string ends with j + 1 ones.

So define dp[i][j] as the number of valid strings of length i that end in exactly j ones. Each cell of row i + 1 is fed by cells of row i, using the two rules above. Row 0 is the starting point: the empty string is the one valid string of length 0, and it ends in 0 ones, so dp[0][0] = 1.

For k = 2 the rows of the table (columns are j = 0, 1, 2) look like this:

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

The answer is the sum of the last row: 7 + 4 + 2 = 13.

Step by step

Create the table. dp has n + 1 rows (lengths 0 to n) and k + 1 columns (0 to k trailing ones), filled with zeros and declared with let mut because the loops write into it.
Seed the empty string: dp[0][0] = 1.
Loop over lengths i from 0 to n - 1, with 0..n. Each pass pushes the counts of length i forward into row i + 1, so the last row written is row n.
Loop over trailing-ones counts j from 0 to k, with 0..=k. The range includes k, because strings ending in exactly k ones are valid.
Append a 0. Every string counted in dp[i][j] becomes a string ending in zero ones, so add dp[i][j] into dp[i + 1][0]. The operator is += because all k + 1 values of j contribute to the same cell.
Append a 1 when allowed. If j < k, add dp[i][j] into dp[i + 1][j + 1]. When j == k, a new 1 would create a run of k + 1 ones, so nothing is added.
Declare result after the loops, starting at 0.
Add up the last row, dp[n][0] through dp[n][k].
Return result as the last expression, with no semicolon.

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

The Rust details worth knowing:

Nested vec!. vec![0; k + 1] makes one row of k + 1 zeros, and vec![row; n + 1] repeats that row n + 1 times, cloning it for each copy. The rows are independent, so writing to one doesn't change the others.
The element type is inferred. The code never writes i32 for the table. Because result is returned as an i32 and gets values from dp, the compiler decides the table holds i32.
Index types. n, k, i and j are all usize, so they index vectors directly with no casts. The parameters are usize because they are sizes of the table.
Half-open versus inclusive ranges. 0..n stops before n, and 0..=k includes k. Mixing them up is the classic off-by-one error in this code.
+= on an element reads and writes the same cell: dp[i + 1][0] += dp[i][j] reads from row i and updates row i + 1. They are different rows, so there is no conflict.
The last expression is the return value. A trailing semicolon after result would make the function return () and fail to compile.

Complexity

Time: O(n × k). The nested loops run n times k + 1 times, with constant work in each step. The final sum adds another O(k). Since k <= n, this is at most O(n²), which is tiny for n = 30.

Space: O(n × k). The table has (n + 1) × (k + 1) cells. Each row depends only on the previous one, so two rows would be enough if memory mattered.

Edge cases and common mistakes

n = 0. The only string is the empty one, so the answer is 1. The loops over 0..n never run, and the last row is row 0.
k = 0. No ones are allowed, so exactly one string works, all zeros. count_binary_strings(3, 0) returns 1.
k = n. Every string is valid, so the answer is 2^n: count_binary_strings(3, 3) returns 8. For n = 30 that is 1,073,741,824, which still fits in an i32 (maximum 2,147,483,647).
Using 0..k for the trailing-ones loop. That skips the column for exactly k ones, and the final sum loses those strings.
Allowing a 1 when j == k. Without the if j < k guard, dp[i + 1][j + 1] is out of range, and the code panics with an index out of bounds.
Declaring result inside a loop. It would reset on every pass and the sum would be wrong.
Forgetting to seed dp[0][0]. With an all-zero table, every entry stays zero and the function returns 0.

Testing

n = 4, k = 2 gives 13.
n = 0, k = 0 gives 1.
n = 1, k = 1 gives 2.
n = 5, k = 1 gives 13, because with no two ones in a row the counts are Fibonacci numbers.
n = 3, k = 3 gives 8.

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

Start learning free