# 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`

.