### PROBLEM LINK:

**Author:** Zi Song Yeoh

### DIFFICULTY:

EASY

### PREREQUISITES:

Dynamic Programming

### PROBLEM:

Given a binary string with some characters replaced with question marks. Find the number of ways to replace the question marks with 1 or 0 so that the resulting string has exactly k runs for all 1 \le k \le n.

### EXPLANATION:

Firstly, the naive solution is to iterate through all possible binary strings and find the number of runs in each of them. This solution will work in O(2^{n} \cdot n) time.

Now, to get a faster solution, we need dynamic programming. Let dp*[j][k] denote the number of ways to fill the question marks from digits 1 to i so that there are exactly j runs and the i-th digit is k. (so k = 0 or 1)

We can easily update the dp by considering all possible values of the current digit.

If the i-th digit can be 1, then dp*[j][1] += dp[i - 1][j - 1][0] + dp[i - 1][j][1].

If the i-th digit can be 0, then dp*[j][0] += dp[i - 1][j - 1][1] + dp[i - 1][j][0].

The time complexity of this solution is O(n^2).

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.