Editorial : Counting Binary Strings

Suppose we have a string containing g good substrings. How does g vary when we append an element?

If you append 1, then the uncounted good substrings are those that end at this 1. If there are y suffix zeroes, then a total of y + 1 new good substrings would appear.

If you append 0, then the uncounted good substrings is equal to 1 + the number of consecutive zeroes to the left of the last occurrence of 1.

Hence, we need to track 2 parameters to quickly compute the answer. Define dp[i][x][y] to be the number of strings that has i good substrings and has a suffix that consists of x zeroes, followed by a single one, followed by y zeroes.

Time Complexity : O(n^3). We have 3 parameters for the DP. Let’s reduce it to 2 to allow scope for optimization.

Let’s define dp[i][x] as the number of strings that contain i good substrings and has exactly x suffix zeroes. We can try extending this string by adding 10000... where the new suffix zeroes would have length y. Of course, x + y < k to ensure that we don’t create a good substring of length greater than k.