Count Ways To Build Good Strings — Medium Problem & Solution

Problem statement

Build a binary string starting from the empty string. At each step you may append zero copies of '0' or one copies of '1'.

A string is good when its length is between low and high inclusive. Return the number of different good strings you can build, modulo 10^9 + 7.

Example 1

Input: low = 3, high = 3, zero = 1, one = 1
Output: 8
Explanation: Every binary string of length 3.

Example 2

Input: low = 2, high = 3, zero = 1, one = 2
Output: 5
Explanation: Length 2 gives "00" and "11"; length 3 gives "000", "011" and "110".

Example 3

Input: low = 1, high = 1, zero = 1, one = 1
Output: 2

Constraints

• 1 <= low <= high <= 100000
• 1 <= zero, one <= high

How to solve Count Ways To Build Good Strings

The state collapses to the length. A string of length i is built by appending a block of zero zeros to a string of length i - zero, or a block of one ones to one of length i - one — and those two cases are disjoint because the final block differs.

Approach

1. Set dp[0] = 1 for the empty string.
2. For i from 1 to high, add dp[i - zero] and dp[i - one] where the indices are valid.
3. Sum dp[i] for i in [low, high], all modulo 10^9 + 7.

Why it works

Every non-empty buildable string ends in exactly one kind of block, so classifying by that block partitions the ways — no double counting and nothing missed. Different build sequences also give different strings, because the blocks are read off the string's own structure from the right.

Complexity

• Time — O(high)
• Space — O(high)

Pitfalls

• The two cases are added, not multiplied — they are alternatives.
• Reducing modulo only at the end overflows; reduce at every addition.
• zero and one may be equal, in which case dp[i] doubles each valid step.

Reference solution

Python

def countGoodStrings(low: int, high: int, zero: int, one: int) -> int:
    MOD = 1000000007
    dp = [0] * (high + 1)
    dp[0] = 1
    ans = 0
    for i in range(1, high + 1):
        if i >= zero:
            dp[i] = (dp[i] + dp[i - zero]) % MOD
        if i >= one:
            dp[i] = (dp[i] + dp[i - one]) % MOD
        if i >= low:
            ans = (ans + dp[i]) % MOD
    return ans

JavaScript

var countGoodStrings = function(low, high, zero, one) {
    var MOD = 1000000007;
    var dp = [];
    for (var t = 0; t <= high; t++) dp.push(0);
    dp[0] = 1;
    var ans = 0;
    for (var i = 1; i <= high; i++) {
        if (i >= zero) dp[i] = (dp[i] + dp[i - zero]) % MOD;
        if (i >= one) dp[i] = (dp[i] + dp[i - one]) % MOD;
        if (i >= low) ans = (ans + dp[i]) % MOD;
    }
    return ans;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More dynamic programming problems

• Minimum Number of Increments on Subarrays to Form a Target Array Medium
• Partition Array for Maximum Sum Medium
• Stone Game VII Medium
• Minimum Number of Work Sessions to Finish the Tasks Medium
• Count Fertile Pyramids in a Land Medium
• Number of Ways to Divide a Long Corridor Medium