MediumNo. 2466
Count Ways To Build Good Strings — LeetCode 2466 Python Solution
- Pattern
- Dynamic Programming
- Topics
- Dynamic Programming
- Reading time
- 3 min
- Source
- leetcode.com
The problem
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.
Example
- Input
- low = 3, high = 3, zero = 1, one = 1
- Output
- 8
- Explanation
- One possible valid good string is "011".
Python solution
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)Complexity
- Time
- O(n)
- Space · auxiliary
- O(n)
Pattern: Dynamic Programming
Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 2466. Count Ways To Build Good Strings is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.
The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 2463 | Minimum Total Distance Traveled | Hard |
| 0010 | Regular Expression Matching | Hard |
| 0022 | Generate Parentheses | Medium |
| 0032 | Longest Valid Parentheses | Hard |
| 0044 | Wildcard Matching | Hard |
| 0045 | Jump Game II | Medium |
Frequently asked questions
- How hard is LeetCode 2466. Count Ways To Build Good Strings?
LeetCode 2466. Count Ways To Build Good Strings is rated Medium on LeetCode.
- What is the time complexity of LeetCode 2466. Count Ways To Build Good Strings?
The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 2466. Count Ways To Build Good Strings?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 2466. Count Ways To Build Good Strings cover?
LeetCode 2466. Count Ways To Build Good Strings is tagged Dynamic Programming on LeetCode.