Posted on

Count Ways To Build Good Strings

Given the integers zeroonelow, 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.

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<sup>9</sup> + 7.

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.

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

Solution: fastest one is using tabulation dynamic programming technique.

    int countGoodStrings(int low, int high, int zero, int one) {
        int sum[100001];
        sum[0] = 1;
        for (int i = 1; i <= high; i++)
        {
            long long sumCur = 0;
            if (i >= zero)
                sumCur += sum[i-zero];
            if (i >= one)
                sumCur += sum[i-one];
            if (sumCur > 0x3000000000000000ll)
                sumCur %= 1000000007;
            sum[i] = sumCur % 1000000007;
        }

        long long sumTotal = 0;
        for (int i = low; i <= high; i++)
            sumTotal += sum[i];
        return sumTotal % 1000000007;
    }

Way slower approach is to use a map in your code for memoization, and a recursive DFS method.

class Solution {
public:
    int countGoodStrings(int low, int high, int zero, int one) {
        map<int, int> dp;
        long mod = pow(10,9) +7;    
        function<int(int)> dfs = [&](int length) -> int{
            
            if( length > high ) return 0;

            if(dp.find(length) != dp.end() )
                return dp[length];

            int count = ( length >= low) ? 1 : 0;
            count = (count + dfs(length + zero)) % mod;
            count = (count + dfs(length + one)) % mod;
            
            return dp[length] = count;
        };

        return dfs(0);    
    }
};