2466. Count Ways To Build Good Strings Solution

The problem

Given the integers zero, one, low, and high, we can construct a string by starting with an empty string, and then at each step perform either of the following:

Append the character '0' zero times.
Append the character '1' one times.

This can be performed any number of times.

A good string is a string constructed by the above process having a length between low and high (inclusive).

Return the number of different good strings that can be constructed satisfying these properties. Since the answer can be large, return it modulo 10⁹ + 7.

Example 1:

Input: low = 3, high = 3, zero = 1, one = 1
Output: 8
Explanation: 
One possible valid good string is "011". 
It can be constructed as follows: "" -> "0" -> "01" -> "011". 
All binary strings from "000" to "111" are good strings in this example.

Example 2:

Input: low = 2, high = 3, zero = 1, one = 2
Output: 5
Explanation: The good strings are "00", "11", "000", "110", and "011".

Constraints:

1 <= low <= high <= 10⁵
1 <= zero, one <= low

Approach overview

Problem Overview: You build binary strings by repeatedly appending blocks of size zero or one. A string is considered good if its final length lies between low and high. The task is to count how many such strings can be constructed. Since the count grows quickly, results are returned modulo 1e9 + 7.

Approach 1: Backtracking (Exponential Time)

This approach explores every possible construction path using recursion. Starting from length 0, recursively append a block of size zero or one and continue building the string. Whenever the current length falls within [low, high], increment the count. Recursion stops when the length exceeds high. This brute-force strategy tries all combinations, which leads to roughly O(2^(high / min(zero, one))) time complexity with O(high) recursion depth space. It demonstrates the problem structure but becomes impractical for large high.

Approach 2: Recursion with Memoization (Top-Down DP)

The repeated subproblem is the number of ways to build a valid string starting from a given length. Cache results for each length so the recursion does not recompute the same states. For a state len, the transitions are len + zero and len + one. Each state is solved once and stored in a memo table. This reduces the time complexity to O(high) with O(high) space for the cache and recursion stack. This version clearly shows the overlapping subproblems typical of dynamic programming and is easier to derive from the brute force recursion.

Approach 3: Bottom-Up Dynamic Programming (Optimal)

Instead of recursion, build the solution iteratively. Let dp[i] represent the number of ways to build a string of length i. Initialize dp[0] = 1 since an empty string is the starting state. For each length i from 1 to high, compute dp[i] by adding contributions from dp[i - zero] and dp[i - one] if those indices are valid. While filling the array, accumulate the answer whenever i lies between low and high. This runs in O(high) time with O(high) space. The iterative DP avoids recursion overhead and is the most common implementation in interviews. It is a classic counting pattern in dynamic programming and closely related to state-transition problems seen with memoization and recursion.

Recommended for interviews: The bottom-up dynamic programming approach is the expected solution. Interviewers want to see recognition of overlapping subproblems and a clean dp[i] state transition. Showing the backtracking idea first demonstrates understanding of the search space, but converting it into an O(high) DP solution shows strong algorithmic thinking.

Approach 1: Dynamic Programming Approach

We can solve this problem using a dynamic programming approach. The idea is to maintain a dp array where dp[i] represents the number of good strings of exact length i. Start with an empty string and attempt to form strings by appending '0's and '1's zero and one times respectively. For each length from low to high, we incrementally calculate the number of ways to achieve that length from smaller lengths and store them in dp[i].

Python

def countGoodStrings(low, high, zero, one):
    MOD = 1000000007
    dp = [0] * (high + 1)
    dp[0] = 1
    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
    return sum(dp[low:high + 1]) % MOD

print(countGoodStrings(3, 3, 1, 1))

Java

public class Main {
    public static final int MOD = 1000000007;

    public static int countGoodStrings(int low, int high, int zero, int one) {
        int[] dp = new int[high + 1];
        dp[0] = 1;
        for (int i = 1; i <= high; i++) {
            if (i - zero >= 0) dp[i] = (dp[i] + dp[i - zero]) % MOD;
            if (i - one >= 0) dp[i] = (dp[i] + dp[i - one]) % MOD;
        }
        int result = 0;
        for (int i = low; i <= high; i++) {
            result = (result + dp[i]) % MOD;
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(countGoodStrings(3, 3, 1, 1));
    }
}

C++

#include <iostream>
#include <vector>
#define MOD 1000000007

using namespace std;

int countGoodStrings(int low, int high, int zero, int one) {
    vector<int> dp(high + 1, 0);
    dp[0] = 1;
    for (int i = 1; i <= high; i++) {
        if (i - zero >= 0) dp[i] = (dp[i] + dp[i - zero]) % MOD;
        if (i - one >= 0) dp[i] = (dp[i] + dp[i - one]) % MOD;
    }
    int result = 0;
    for (int i = low; i <= high; i++) {
        result = (result + dp[i]) % MOD;
    }
    return result;
}

int main() {
    cout << countGoodStrings(3, 3, 1, 1) << endl;
    return 0;
}

JavaScript

function countGoodStrings(low, high, zero, one) {
    const MOD = 1000000007;
    const dp = Array(high + 1).fill(0);
    dp[0] = 1;
    for (let 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;
    }
    let result = 0;
    for (let i = low; i <= high; i++) {
        result = (result + dp[i]) % MOD;
    }
    return result;
}

console.log(countGoodStrings(3, 3, 1, 1));

#include <stdio.h>
#define MOD 1000000007

int countGoodStrings(int low, int high, int zero, int one) {
    int dp[high + 1];
    dp[0] = 1; // Base case
    for (int i = 1; i <= high; i++) {
        dp[i] = 0;
        if (i - zero >= 0) dp[i] = (dp[i] + dp[i - zero]) % MOD;
        if (i - one >= 0) dp[i] = (dp[i] + dp[i - one]) % MOD;
    }
    int result = 0;
    for (int i = low; i <= high; i++) {
        result = (result + dp[i]) % MOD;
    }
    return result;
}

int main() {
    int low = 3, high = 3, zero = 1, one = 1;
    printf("%d\n", countGoodStrings(low, high, zero, one));
    return 0;
}

using System;

class Program {
    const int MOD = 1000000007;

    static int CountGoodStrings(int low, int high, int zero, int one) {
        int[] dp = new int[high + 1];
        dp[0] = 1;
        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;
        }
        int result = 0;
        for (int i = low; i <= high; i++) {
            result = (result + dp[i]) % MOD;
        }
        return result;
    }

    static void Main() {
        Console.WriteLine(CountGoodStrings(3, 3, 1, 1));
    }
}

This Python solution implements the DP approach where we maintain a list dp to store the number of valid strings of each possible length. Using a loop, we calculate possible strings by adding previous results. Finally, we sum the relevant part of the list to get the total answer.

Complexity

Time Complexity: O(high)
Space Complexity: O(high)

Try this approach in the editor

Approach 2: Backtracking Approach

In this approach, we explore every possible string configuration using backtracking to find strings whose lengths fall between low and high. We use recursion to build strings by appending zero or one '0's and '1's, tracking lengths and adding valid ones to a result set. Although not as efficient as the DP method due to exponential complexity, it serves as an insightful means to intuitively grasp the construction of such strings.

Python

def countGoodStrings(low, high, zero, one):
    MOD = 1000000007
    good_count = 0

    def backtrack(length):
        nonlocal good_count
        if low <= length <= high:
            good_count = (good_count + 1) % MOD
        if length > high:
            return
        backtrack(length + zero)
        backtrack(length + one)

    backtrack(0)
    return good_count

print(countGoodStrings(3, 3, 1, 1))

The backtracking solution in Python employs a recursive function to consider adding either zero or one characters to a string. It tracks the length of each created string and counts those which are valid. Once a length exceeds high, recursion stops further exploration from that branch.

Complexity

Time Complexity: O(2^n) where n is high / min(zero, one)
Space Complexity: O(n) because of the recursion stack

Try this approach in the editor

Approach 3: Memoization Search

We design a function dfs(i) to represent the number of good strings constructed starting from the i-th position. The answer is dfs(0).

The computation process of the function dfs(i) is as follows:

If i > high, return 0;
If low leq i leq high, increment the answer by 1, then after i, we can add either zero number of 0s or one number of 1s. Therefore, the answer is incremented by dfs(i + zero) + dfs(i + one).

During the process, we need to take the modulus of the answer, and we can use memoization search to reduce redundant computations.

The time complexity is O(n), and the space complexity is O(n). Here, n = high.

func countGoodStrings(low int, high int, zero int, one int) int {
	f := make([]int, high+1)
	for i := range f {
		f[i] = -1
	}
	const mod int = 1e9 + 7
	var dfs func(i int) int
	dfs = func(i int) int {
		if i > high {
			return 0
		}
		if f[i] != -1 {
			return f[i]
		}
		ans := 0
		if i >= low && i <= high {
			ans++
		}
		ans += dfs(i+zero) + dfs(i+one)
		ans %= mod
		f[i] = ans
		return ans
	}
	return dfs(0)
}

Try this approach in the editor

Approach 4: Dynamic programming

TypeScript

function countGoodStrings(low: number, high: number, zero: number, one: number): number {
    const mod = 10 ** 9 + 7;
    const f: number[] = new Array(high + 1).fill(0);
    f[0] = 1;

    for (let i = 1; i <= high; i++) {
        if (i >= zero) f[i] += f[i - zero];
        if (i >= one) f[i] += f[i - one];
        f[i] %= mod;
    }

    const ans = f.slice(low, high + 1).reduce((acc, cur) => acc + cur, 0);

    return ans % mod;
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Dynamic Programming Approach	Time Complexity: `O(high)` Space Complexity: `O(high)`
Backtracking Approach	Time Complexity: `O(2^n)` where `n` is `high` / min(zero, one) Space Complexity: `O(n)` because of the recursion stack
Memoization Search	–
Dynamic programming	–

Complexity analysis

Approach	Time	Space	When to Use
Backtracking	Exponential	O(high)	Useful for understanding the brute-force search tree and generating all possible constructions.
Recursion + Memoization	O(high)	O(high)	Good when deriving the DP from recursion and eliminating repeated subproblems.
Bottom-Up Dynamic Programming	O(high)	O(high)	Preferred interview solution. Iterative, simple state transitions, and no recursion overhead.

Frequently asked questions

Is Count Ways To Build Good Strings easy or hard?

Count Ways To Build Good Strings is classified as Medium difficulty. The main challenge is recognizing the dynamic programming state transition and avoiding exponential recursion by storing results for each length.

Count Ways To Build Good Strings Python/Java solution

Both Python and Java implementations use the same DP idea. Create an array dp of size high + 1, initialize dp[0] = 1, and iteratively update dp[i] using dp[i - zero] and dp[i - one]. Add dp[i] to the result when i lies between low and high, applying modulo 1e9+7.

How to solve Count Ways To Build Good Strings in O(n)?

Treat each possible length as a DP state. Initialize dp[0] = 1 and iterate from 1 to high. For each i, add contributions from dp[i - zero] and dp[i - one] if those indices are valid. Sum dp[i] for all i in the range [low, high]. This produces an O(high) time solution.

What is the best approach for Count Ways To Build Good Strings?

The best approach is bottom-up dynamic programming. Define dp[i] as the number of ways to build a string of length i, then transition using dp[i - zero] and dp[i - one]. This computes all states up to high in O(high) time and O(high) space while accumulating valid lengths between low and high.

Is Count Ways To Build Good Strings asked at Google/Amazon/Meta?

This problem represents a common dynamic programming counting pattern frequently seen in interviews at large tech companies. Variations of length-based DP and state transitions appear in Google, Amazon, and Meta interview question sets.

What data structure is used in Count Ways To Build Good Strings?

The core data structure is a one-dimensional dynamic programming array where dp[i] stores the number of ways to construct a string of length i. Recursion with memoization may also use a hash map or array cache to store computed states.

What is the time complexity of Count Ways To Build Good Strings?

The optimal dynamic programming solution runs in O(high) time because each length from 1 to high is processed once. Space complexity is also O(high) for the DP array storing the number of ways to reach each length.

Count Ways To Build Good Strings solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming Approach

Approach 2: Backtracking Approach

Approach 3: Memoization Search

Approach 4: Dynamic programming

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Count Ways To Build Good Strings solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming Approach

Approach 2: Backtracking Approach

Approach 3: Memoization Search

Approach 4: Dynamic programming

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems