We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Ways To Build Good Strings

Difficulty: Medium

Problem Description

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^9 + 7.

Key Insights

  • We can use dynamic programming to keep track of the number of good strings of a certain length.
  • The state of our DP array will represent the number of ways to construct strings of specific lengths.
  • The transition will involve adding strings of length zero (by appending '0') and strings of length one (by appending '1').
  • We only need to consider lengths from low to high.

Space and Time Complexity

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

Solution

We will use a dynamic programming approach where we maintain an array dp where dp[i] represents the number of ways to construct a string of length i. We will iterate through lengths from 0 to high and calculate the number of ways to reach each length using the values of previous lengths, specifically dp[i-zero] and dp[i-one]. We accumulate the results for lengths between low and high to get the final answer.

Code Solutions

def countGoodStrings(low, high, zero, one):
    MOD = 10**9 + 7
    dp = [0] * (high + 1)
    dp[0] = 1  # There's one way to create an empty string

    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

    # Sum the counts of good strings between lengths low and high
    return sum(dp[low:high + 1]) % MOD
← Back to All Questions