LESSON 320 OF 347 · FREE CODING INTERVIEW QUESTIONS

Binary Strings With At Most K Consecutive Ones in C#: DP in O(N*K)

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

C# · FREE CODING INTERVIEW QUESTIONS

Binary Strings With At Most K Consecutive Ones in C#, explained

Problem overview

The method CountBinaryStrings takes two non-negative integers, n and k, with k <= n <= 30. It returns how many binary strings of length n never contain more than k ones in a row.

For n = 4 and k = 2 there are 16 strings of length 4, and three of them break the rule: 0111, 1110 and 1111 each contain three ones in a row. The answer is 16 - 3 = 13.

Approach: build strings one character at a time

Listing all 2^n strings and checking each one is the brute force. With n up to 30 that is over a billion strings, which is too slow. Dynamic programming counts the strings without listing them.

To decide whether a new character is allowed, you only need to know how many ones the string currently ends with. So define dp[i, j] as the number of valid strings of length i that end in exactly j ones. Every valid string has j between 0 and k.

Take a string counted in dp[i, j] and append one character:

Append 0. The run of ones is broken, so the new string of length i + 1 ends in 0 ones. This is always allowed.
Append 1. The run grows to j + 1. This is allowed only when j < k.

Every valid string of length i + 1 comes from exactly one valid string of length i by one of these two moves, so no string is missed or counted twice. The answer is the sum of row n.

For n = 4 and k = 2 the table, with columns j = 0, 1, 2, is:

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

You can check one cell by hand. dp[3, 1] is 2: the length-3 strings ending in exactly one 1 are 001 and 101. It comes from appending a 1 to the two strings in dp[2, 0], which are 00 and 10. The last row sums to 7 + 4 + 2 = 13, which matches the example.

Step by step

Create the table as a rectangular int[,] with n + 1 rows (lengths 0 to n) and k + 1 columns (0 to k trailing ones). C# fills a new numeric array with zeros.
Seed it: dp[0, 0] = 1. The empty string is the one string of length 0, and it ends in zero ones. Every other string grows from it.
Loop over lengths i from 0 to n - 1. The body writes into row i + 1, so the last row, n, is only written, never used as a source.
Loop over j from 0 to k, inclusive, since strings can end in up to k ones.
Append a 0: add dp[i, j] into dp[i + 1, 0]. Use +=, because every value of j feeds that same cell.
Append a 1 only if j < k: add dp[i, j] into dp[i + 1, j + 1]. Without the guard the index k + 1 would fall outside the table, and the strings would break the limit anyway.
Declare result as 0 after the loops, then add each dp[n, j] for j from 0 to k into it.
Return result.

The solution in C#

class Solution {
    public int CountBinaryStrings(int n, int k) {
        int[,] dp = new int[n + 1, k + 1];
        dp[0, 0] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= k; j++) {
                dp[i + 1, 0] += dp[i, j];
                if (j < k) {
                    dp[i + 1, j + 1] += dp[i, j];
                }
            }
        }
        int result = 0;
        for (int j = 0; j <= k; j++) {
            result += dp[n, j];
        }
        return result;
    }
}

The C# details worth knowing:

Rectangular array. new int[n + 1, k + 1] creates a table whose cells are read and written as dp[i, j]. Every cell starts at 0, so += works from the first use with no setup.
+= on an array cell. dp[i + 1, 0] += dp[i, j] is the same as writing the cell on both sides of an assignment. The index expression is evaluated once.
Sizes in the declaration, not the type. The type is int[,], and the lengths appear only in the new expression. Out-of-range indexes throw an IndexOutOfRangeException instead of reading garbage.
Overflow is not a concern here. Each count is at most 2^n, and 2^30 is 1,073,741,824, below int.MaxValue (2,147,483,647). For n = 31 the total could pass the int range; C# would then wrap around silently, so a long would be needed.

Complexity

Time: O(n * k). The nested loops run n times k + 1 iterations, with constant work each. The final sum adds O(k).

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

k = 0. No ones are allowed, so only the all-zero string is valid, and the answer is 1. The table has one column and the j < k test is never true.
k = n. Every string is valid, so the answer is 2^n. For n = 3, k = 3 it returns 8.
n = 0. The loops don't run and dp[0, 0] is 1, so the empty string is counted once.
Small checks. n = 3, k = 1 returns 5: 000, 001, 010, 100, 101.
Looping i up to n. dp[i + 1, ...] would then write to row n + 1, which does not exist.
Using = instead of +=. Each pass over j would overwrite dp[i + 1, 0], keeping only the last term.
Forgetting the j < k guard. It either crashes with an out-of-range index or counts invalid strings.
Summing the whole table. Only the last row counts strings of length n.

Testing

n = 4, k = 2 gives 13.
n = 3, k = 1 gives 5.
n = 3, k = 3 gives 8.
n = 5, k = 0 gives 1.
n = 1, k = 1 gives 2.

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

Start learning free