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[i][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[i][j][1] += dp[i - 1][j - 1][0] + dp[i - 1][j][1].
If the i-th digit can be 0, then dp[i][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.
