Count Ways to Build Good Strings - Leetcode 2466 - Python

Solving Leetcode 2466 - Count Ways to build Good strings, today's daily leetcode problem on May 12.
🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
Problem Link: leetcode.com/problems/count-w...
0:00 - Read the problem
0:30 - Intuition
2:50 - Explaining Decision Tree
7:48 - Coding Memoization
10:40 - Coding Tabulation
leetcode 2466
#neetcode #leetcode #python

[@anand.prasad502]

3:18 Ans is "NO", it is length of string not the string, so it can be different. "000" and "100" result can be different;

[@rowanus116]

regardless of previous string formulation as long as they have the same length, the decision is the same, either choose 0 or 1, that's why caches work here.

[@deadlyecho]

Can we solve using a combinatorics approach ?

[@uptwist2260]

thanks for the daily

[@abaddon6206]

Can we do this problem using brute force and applying permutation and combination. Because in this problem all we have to find is the combination of the good string?

[@DavidDLee]

If you go backwards in the iterative solution, the result is dp[0]. However, you can't just set dp[high] = 1 and keep everything else 0.
Also, in the general case, max(dp[low:high + 1]) might be > 1.

[@shubhaverma5697]

i think my mind broke when you went from backtracking to linked list lol

[@aniketmahangare8333]

Thank you so much man.

[@ronbuchanan5432]

What's the time complexity?

[@kaushik.aryan04]

This was a really good question

[@TheNishant30]

one of the test cases blows up the javascript stack even with memoization. low is 100000, high is 100000, zero is 2 and one is 8.

[@ouchlock]

spent an hour with permutation approach, and it turned out to be so simple, muahh %(

[@blazze_]

Bro is so emotional when explaining the problem.

[@MP-ny3ep]

Thank you!

[@arpanbanerjee6224]

Great exoplanation as usual-
java solution
class Solution {
Integer[] dp = null;
int mod= 1000000007;
private int helper(int low, int high, int zero, int one, int currLen){
if(currLen>high) return 0;
if(dp[currLen]!=null) return dp[currLen];
int res=0;
// if within range we wll include this string
if(currLen>=low){
res=1;
}else{
res=0;
}
res+= helper(low,high,zero,one,currLen+zero)%mod
+helper(low,high,zero,one,currLen+one)%mod;
dp[currLen]=res%mod;
return dp[currLen];
}
public int countGoodStrings(int low, int high, int zero, int one) {
dp=new Integer[high+1];
return helper(low,high,zero,one,0);
}
}

[@krateskim4169]

Thank you so much

[@sandeepmourya8922]

Hey NeetCode or anyone reading this, I really need your help I cannot find single resource for good explanation of this problem:
2673. Make Costs of Paths Equal in a Binary Tree (It has no editorial on Leetcode)
Everyone has almost used the same solution
int minIncrements(int n, vector& cost) {
int res = 0;
function dfs = [&](int i) {
if (i >= cost.size()) return 0;
int a = dfs(2 * i + 1), b = dfs(2 * i + 2);
res += abs(a - b);
return cost[i] + max(a, b);
};
dfs(0);
return res;
}
But NOOOOO one explains clearly whyy do we have to return cost[i] + max(a, b). Any help from anyone in the comments section will be appreciated.

[@kaushik.aryan04]

You explained it really well but the code in python is very different when compared to java or c++
This is my code in java ( tabulation)
class Solution {
int mod = 1000000007;
int[] dp ;
public int countGoodStrings(int low, int high, int zero, int one) {
dp = new int[high + Math.max(high , low) + 5];
// filling base case array
for(int i = 0 ; i < high + 5 ; i++){
if(i >= low && i high) dp[i] = 0;
}
for(int i = high ; i >= 0 ; i--){
int left = dp[i+ zero] % mod;
int right = dp[i + one] % mod;
dp[i] = dp[i]+ (left+ right) % mod;
}
return dp[0];
}
}

[@mohdmaaz6651]

Java Solution using HashMap:
public int countGoodStrings(int low, int high, int zero, int one) {
int mod = (int) 1e9+7;
HashMap dp = new HashMap();
for(int i=high; i>=0; --i){
if(i>=low) dp.put(i, (1+dp.getOrDefault(i+zero, 0)+dp.getOrDefault(i+one, 0))%mod);
else dp.put(i, (dp.getOrDefault(i+zero, 0)+dp.getOrDefault(i+one, 0))%mod);
}
return dp.get(0);
}

[@amalvijay8222]

1st comment and big fan

[@GameFlife]

bruh say feel good until tmr xDD

[@name_surname_1337]

do you know that fb doesn't ask DP at all? stop doing these fake thumbnails pls