Count Ways To Build Good Strings

Problem Statement

In this problem, you are given four integers: zero, one, low, and high. The problem revolves around constructing binary strings that start from an empty string. At each construction step, you can choose to:

1. Append the character '0', exactly zero times to the current string.
2. Append the character '1', exactly one times to the string.

These operations can be executed any number of times sequentially in any order. A string is classified as good if its total length lies between the range defined by low and high (inclusive).

Your goal is to compute the total number of distinct good strings that can be created using the above rules. Due to potentially large outcomes, the final result should be presented modulo 10^9 + 7.

Examples

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 <= 105
• 1 <= zero, one <= low

Approach and Intuition

To tackle the problem effectively, let's dissect how strings are constructed and determine their uniqueness based on the provided examples:

Example 1

Input Parameters:

• low = 3, high = 3
• zero = 1, one = 1

Output:

• Total good strings: 8

Steps and Strategy:

• For this input scenario, all possible binary strings of length 3 ("000" to "111") meet the conditions for being good strings because the conditions allow adding either one '0' or one '1' to the string repeatedly.

• The strategy involves generating combinations of the characters '0' and '1', adhering strictly to the limits of low and high while respecting the specific repetition allowed for '0' and '1' (which is 1 in both cases here). This makes it straightforward since every possible combination is valid.

Example 2

Input Parameters:

• low = 2, high = 3
• zero = 1, one = 2

Output:

• Total good strings: 5

Steps and Strategy:

• The focus here shifts to variations between lengths of 2 and 3:

  • For length 2, the strings "00" and "11" are valid (note: '1' is appended twice, so "11").
  • For length 3, the valid strings are "000", "110", and "011".

• This example illustrates that not every binary permutation is valid, but rather those that respect the number of repetitions detailed by zero and one parameters.

In a generalized approach:

• Define the function to recursively generate strings based on the specified constraints, accounting for low to high string lengths.
• Ensure that sequences are unique through the mixture of '0's and '1's as prescribed, tracking instances where the character count matches the allowed append count.
• Maintain a count of such unique sequences within the defined bounds and utilize modulo arithmetic to handle large numbers as required by problem constraints.

Through these steps, the problem translates into recursive combinations and modulate counting in adherence to the problem's strict rules.

Solutions

class Solution {
    int[] memo;
    int modulo = 1_000_000_007;
        
    private int countSequences(int length, int zeros, int ones) {
        if (memo[length] != -1) {
            return memo[length];
        }
            
        int result = 0;
        if (length >= ones) {
            result += countSequences(length - ones, zeros, ones);
        }
        if (length >= zeros) {
            result += countSequences(length - zeros, zeros, ones);
        }
        memo[length] = result % modulo;
        return memo[length];
    }
        
    public int findNumberOfGoodStrings(int minLen, int maxLen, int zeros, int ones) {
        memo = new int[maxLen + 1];
        Arrays.fill(memo, -1);
        memo[0] = 1;
    
        int sum = 0;
        for (int i = minLen; i <= maxLen; ++i) {
            sum += countSequences(i, zeros, ones);
            sum %= modulo;
        }
        return sum;
    }
}