Count Ways To Build Good Strings

Medium
871.

Count Ways To Build Good Strings

Count Ways To Build Good Strings is a medium coding problem on dynamic programming, asked in Amazon, Google and Salesforce interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} low
 * @param {number} high
 * @param {number} zero
 * @param {number} one
 * @return {number}
 */
var countGoodStrings = function(low, high, zero, one) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Ways To Build Good Strings — Problem & Solution

Count Ways To Build Good Strings solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Count Ways To Build Good Strings is a medium coding problem on dynamic programming, asked in Amazon, Google and Salesforce interviews.

  • Difficulty: Medium
  • Topics: Dynamic Programming
  • Asked at: Amazon, Google, Salesforce
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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

Hints for Count Ways To Build Good Strings

  1. Hint 1

    Only the current length matters — the actual characters never constrain the next step.

  2. Hint 2

    dp[i] is the number of ways to build a string of length exactly i.

  3. Hint 3

    dp[i] = dp[i - zero] + dp[i - one], and the answer sums dp[i] over low ≤ i ≤ 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

Java

public static int countGoodStrings(int low, int high, int zero, int one) {
    final int MOD = 1000000007;
    int[] dp = new int[high + 1];
    dp[0] = 1;
    int ans = 0;
    for (int 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;
}

C++

int countGoodStrings(int low, int high, int zero, int one) {
    const int MOD = 1000000007;
    vector<int> dp(high + 1, 0);
    dp[0] = 1;
    int ans = 0;
    for (int 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;
}

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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 402 dynamic programming problems · the whole catalogue

Learn the technique: Dynamic Programming