#2466

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Count Ways To Build Good Strings

Count the number of ways to build good binary strings using dynamic programming with state transitions.

Problem Statement

You are given four integers: zero, one, low, and high. Starting with an empty string, you can repeatedly perform two operations: append '0' to the string (up to zero times) or append '1' to the string (up to one time). The goal is to compute the number of valid binary strings that have a length between low and high, inclusive.

A valid string is one that can be constructed by following the above operations. The problem asks you to calculate how many such valid strings exist within the given length constraints using dynamic programming.

Examples

Example 1

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

Output: 8

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

The good strings are "00", "11", "000", "110", and "011".

Constraints

1 <= low <= high <= 105
1 <= zero, one <= low

Solution Approach

State Transition Dynamic Programming

By treating the number of strings as states, this problem can be solved by calculating the number of ways to reach a string of each length. Start from the base case (an empty string) and apply the operations step by step while keeping track of valid strings in the range from low to high.

Iterative DP Solution

Iteratively calculate the number of valid strings for each possible length from 0 to high. Use a dynamic programming array to store the number of ways to form a string of a given length, and then transition based on appending '0' or '1'.

Optimizing Space Complexity

Since we only need information about the previous state and the current state, we can optimize space by storing just the current and previous values of the DP array, reducing space complexity from O(high) to O(1).

Complexity Analysis

Metric	Value
Time	O(\text{high})
Space	O(\text{high})

The time complexity of this approach is O(high) as we iterate through the lengths from 0 to high. The space complexity is O(high) without optimization and O(1) with space optimization by keeping track of only necessary states at each step.

What Interviewers Usually Probe

Look for the candidate's understanding of dynamic programming and state transitions.
Check if the candidate can optimize the space complexity by reducing it to O(1).
Evaluate whether the candidate can describe how to handle the edge cases like when low equals high.

Common Pitfalls or Variants

Common pitfalls

Overcomplicating the space complexity by not using the state transition optimization.
Not handling the case where low equals high correctly, leading to incorrect counting.
Confusing the number of valid strings with the number of operations to generate them.

Follow-up variants

Adjust the problem to only count strings with a fixed length instead of a range.
Introduce a limit on the number of '1' or '0' that can be appended at each step.
Extend the problem to include additional binary operations or different characters.

FAQ

How do I approach the Count Ways To Build Good Strings problem?

Start by applying dynamic programming to calculate the number of ways to form valid strings using state transitions, then optimize for space complexity.

What is the time complexity of solving this problem?

The time complexity is O(high) because you calculate the valid strings for each length from 0 to high.

How can I optimize the space complexity of this problem?

You can optimize space by only storing the current and previous states, reducing space complexity from O(high) to O(1).

What are common mistakes when solving this problem?

Common mistakes include not handling edge cases, such as when low equals high, or not optimizing the space complexity.

Can the problem be extended to other types of strings?

Yes, you can modify the problem to count strings with a fixed length, or introduce other operations or characters beyond binary digits.

terminal

Solution

Solution 1: Memoization Search

We design a function $dfs(i)$ to represent the number of good strings constructed starting from the $i$-th position. The answer is $dfs(0)$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:
        @cache
        def dfs(i):
            if i > high:
                return 0
            ans = 0
            if low <= i <= high:
                ans += 1
            ans += dfs(i + zero) + dfs(i + one)
            return ans % mod

        mod = 10**9 + 7
        return dfs(0)

Solution 2: Dynamic programming

#### TypeScript

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:
        @cache
        def dfs(i):
            if i > high:
                return 0
            ans = 0
            if low <= i <= high:
                ans += 1
            ans += dfs(i + zero) + dfs(i + one)
            return ans % mod

        mod = 10**9 + 7
        return dfs(0)

Continue Practicing

#2463 minimum total distance traveled #2472 maximum number of non overlapping palindrome substrings #2478 number of beautiful partitions