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:
'0' zero times.'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 109 + 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 <= 1051 <= zero, one <= lowWe 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].
The solution uses dynamic programming with an array dp where dp[i] stores the number of valid ways to form a string of length i. We start by initializing dp[0] to 1, which serves as our base case. From there, we loop through each length from 1 to high and calculate dp[i] as the sum of dp[i-zero] and dp[i-one], taking care to only add values when the indices are valid. Finally, we sum up all dp[i] from low to high to get our result.
C++
Java
Python
C#
JavaScript
Time Complexity: O(high)
Space Complexity: O(high)
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.
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.
Time Complexity: O(2^n) where n is high / min(zero, one)
Space Complexity: O(n) because of the recursion stack
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: |
| Backtracking Approach | Time Complexity: |
Count Ways to Build Good Strings - Leetcode 2466 - Python • NeetCodeIO • 10,086 views views
Watch 9 more video solutions →Practice Count Ways To Build Good Strings with our built-in code editor and test cases.
Practice on FleetCode