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.

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.prasad]

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;

[rowanus]

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.

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

[TheNishant]

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

[shubhaverma]

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

[ouchlock]

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

[piappl]

Bro is so emotional when explaining the problem.

[arpanbanerjee]

Great exoplanation as usual-
java solution

class Solution {
Integer[] dp = null;
int mod=
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);
}
}

[deadlyecho]

Can we solve using a combinatorics approach ?

[abaddon]

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?

[sandeepmourya]

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<int>& cost) {
int res = 0;
function<int(int)> 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 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.aryan]

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 =
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] = 1;
}
if(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];
}

}