Count Ways To Build Good Strings - Practice Coding Problems

Count Ways To Build Good Strings - Problem

Dynamic Programming Medium

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.

Input & Output

Example 1 — Basic Case

$ Input: zero = 1, one = 1, low = 2, high = 3

› Output: 2

💡 Note: We can build strings of length 2 and 3: '00' (add 1 zero twice), '11' (add 1 one twice). Total = 2 good strings.

Example 2 — Different Step Sizes

$ Input: zero = 2, one = 3, low = 6, high = 7

› Output: 5

💡 Note: Length 6: '000000' (3×zero), '000111' (zero+one), '111000' (one+zero). Length 7: '0000111' (zero+zero+one), '1110000' (one+zero+zero). Total = 5.

Example 3 — Single Valid Length

$ Input: zero = 1, one = 2, low = 3, high = 3

› Output: 2

💡 Note: Only length 3 is valid: '000' (3×zero), '011' (zero+one). Total = 2 good strings.

Constraints

1 ≤ zero, one ≤ 50
1 ≤ low ≤ high ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

zero=1, one=1, low=2, high=3 (can add 1 zero or 1 one at each step)

Process

Build all possible string lengths from 0 to high

Output

Count strings with length in [low, high] range

Key Takeaway

🎯 Key Insight: Use DP to count ways to reach each length, then sum the counts for lengths in [low, high] range

Asked in

G Google 25 f Meta 18 a Amazon 15

The key insight is that this is a dynamic programming problem where each string length can be reached by adding 'zero' zeros or 'one' ones to shorter strings. Best approach is bottom-up DP with Time: O(high), Space: O(high).

Common Approaches

Approach	Time	Space	Notes
✓ Recursive Brute Force	O(2^(high/min(zero,one)))	O(high/min(zero,one))	Generate all possible strings recursively and count those with valid lengths
Memoized Recursion	O(high)	O(high)	Add memoization to avoid recalculating the same subproblems in recursion
Bottom-Up Dynamic Programming	O(high)	O(high)	Build solution iteratively from length 0 to high using 1D DP array

Recursive Brute Force — Algorithm Steps

Start with empty string (length 0)
At each step, try adding 'zero' zeros or 'one' ones
If current length is in [low, high], increment count
Continue until length exceeds high

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin with empty string (length 0)

Branch

At each step, try adding 'zero' zeros or 'one' ones

Count

Count valid strings with length in [low, high] range

Code -

solution.c — C

#include <stdio.h>

const int MOD = 1000000007;

int dfs(int length, int zero, int one, int low, int high) {
    if (length > high) {
        return 0;
    }
    
    long long count = 0;
    if (low <= length && length <= high) {
        count = 1;
    }
    
    // Add 'zero' zeros or 'one' ones
    count += dfs(length + zero, zero, one, low, high);
    count += dfs(length + one, zero, one, low, high);
    
    return count % MOD;
}

int solution(int zero, int one, int low, int high) {
    return dfs(0, zero, one, low, high);
}

int main() {
    int zero, one, low, high;
    scanf("%d", &zero);
    scanf("%d", &one);
    scanf("%d", &low);
    scanf("%d", &high);
    
    int result = solution(zero, one, low, high);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^(high/min(zero,one)))

Each step has 2 choices, creating exponential branching with depth proportional to high

✓ Linear Growth

Space Complexity

O(high/min(zero,one))

Recursion stack depth is proportional to maximum number of steps needed

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Recursive Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler