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

[@uptwist2260]

thanks for the daily

[@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;

[@deadlyecho]

Can we solve using a combinatorics approach ?

[@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.

[@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?

[@aniketmahangare8333]

Thank you so much man.

[@shubhaverma5697]

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

[@MP-ny3ep]

Thank you!

[@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.

[@kaushik.aryan04]

This was a really good question

[@krateskim4169]

Thank you so much

[@ronbuchanan5432]

What's the time complexity?

[@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.

[@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.

[@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); } }

[@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