LeetCode Entry
2466. Count Ways To Build Good Strings
Ways to make 01-string length of low..high programming
2466. Count Ways To Build Good Strings medium
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/848
Problem TLDR
Ways to make 01-string length of low..high #medium #dynamic_programming
Intuition
Let’s observe what happens when we adding zeros and ones:
// "0" "11" -> 00 011 110 1111
// 00 111 -> 00 111 00111 111111 0000 11100
// 000 111 -> 000 111 000111 111000 000000 111111
// * .
// 000111000 000111111
// .
// 111000000 111000111
- each new string is a start of another tree of possibilities
- only the length of this string matters
Let’s do a full Depth-First search, give the current length add zeros or add ones and count the total ways. The result can be cached by the key of the starting length.
Approach
- top-down can be rewritten to the bottom-up DP
- then we can reverse the order of iteration
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(n)\)
Code
val dp = HashMap<Int, Long>()
fun countGoodStrings(low: Int, high: Int, zero: Int, one: Int, len: Int = 0): Long =
if (len > high) 0L else dp.getOrPut(len) {
val addZeros = countGoodStrings(low, high, zero, one, len + zero)
val addOnes = countGoodStrings(low, high, zero, one, len + one)
((if (len < low) 0 else 1) + addZeros + addOnes) % 1_000_000_007L
}
pub fn count_good_strings(low: i32, high: i32, zero: i32, one: i32) -> i32 {
let mut dp = vec![0; 1 + high as usize];
for len in 0..=high as usize {
let add_zeros = dp.get(len - zero as usize).unwrap_or(&0);
let add_ones = dp.get(len - one as usize).unwrap_or(&0);
let curr = (low + len as i32 <= high) as usize;
dp[len] = (curr + add_zeros + add_ones) % 1_000_000_007
}; dp[high as usize] as i32
}
int countGoodStrings(int low, int high, int zero, int one) {
int dp[100001];
for (int l = 0; l <= high; ++l) dp[l] = ((low + l <= high) +
(l < zero ? 0 : dp[l - zero]) +
(l < one ? 0 : dp[l - one])) % 1000000007;
return dp[high];
}