Number of Ways to Form a Target String Given a Dictionary | Recur | Memo | Leetcode 1639 | MIK

[@ManojKrVerma-vw4dx]

U are awesome man. U made it look so easy and intuitive.

[@codestorywithMIK]

Thanks a lot Manoj ❤️❤️❤️

[@akashcodeeerrrr]

No words for your Explanation 🤯 Thanks Mik -> GOAT OF DSA ❤

[@souravjoshi2293]

You are awesome. No one can make Hard problem this easy. You have a gifted technique of teaching.

[@muditgoel3026]

Great explanation

[@elakstein]

You are doing a great job, all of this can be monetized but you are giving it all for free. Thanks.

[@codestorywithMIK]

So glad you liked it ❤️❤️❤️ Thank you so much for taking out time to watch my videos

[@yashchamoli8695]

God promise bahiya apse aacha kisise smj nhi aayaaaa❤️🙏🏻 Thank you bhaiya

[@codestorywithMIK]

Thank you so so much Yash. Made my day ❤️

[@iamnoob7593]

Man what an explanation , Just of the world.

[@India_mera_sabkuch]

Greatest of all time!!

[@damagedhumor]

Awesome explanation, loved it, thanks ❤

[@JitBanerjee-t7c]

Bro your explanation is god level 🔥

[@anuppatankar4294]

Great Video

[@codestorywithMIK]

Thanks a lot Anup ❤️❤️

[@AnujSharma-ro4kc]

bro u made it sooo simple. thanks man

[@codestorywithMIK]

Thanks a lot Anuj ❤️❤️❤️

[@VsEdits59]

idea of freq matrix is too good , was thinking to check characters of dictinoary and target

[@sidharthdhiman4522]

man you are great , you made this tough question so much simple , respect++;

[@codestorywithMIK]

Thank you so much Sidharth ❤️

[@sidharthdhiman4522]

@@codestorywithMIK I have send the connection request to you on LinkedIn .

[@simardeepsinghmudhar7065]

Your explanations are fantastic, keep up the good work subscribed 👍

[@codestorywithMIK]

Welcome to my small channel and thank you so much 😊

[@04shreyasupekar8]

very well explained! Thank you

[@codestorywithMIK]

Glad it was helpful!😇🙏

[@ayushmanbaghel7659]

Bro Nice explanation

[@aizad786iqbal]

u make even hard look easy... btw int MOD = (int)1e9+7; I think this is easier to write

[@codestorywithMIK]

Perfect 😇❤️

[@jewelchakraborty9717]

Hi Mik, thanks for your wonderful explanation. I am providing all my JAVA solutions here right from Memo -> Tabulation -> Space optimization from 2D dp array to two(prev array and curr array) 1D dp array -> Space Optimization from two 1D dp array to only one 1D dp array(only prev array) which is the most optimal solution. Please comment if you like my approaches or if you have any doubts. /* MEMO */ class Solution { int n, m, k; long[][] freq, dp; int mod = (int)1e9 + 7; public long solve(int idx, String[] a, int targIdx, String targ){ if(targIdx >= m) return 1; if(idx >= k) return 0; if(dp[idx][targIdx] != -1) return dp[idx][targIdx] % mod; long notpick = solve(idx + 1, a, targIdx, targ) % mod; long pick = freq[targ.charAt(targIdx) - 'a'][idx] * (solve(idx + 1, a, targIdx + 1, targ) % mod); return dp[idx][targIdx] = (notpick + pick) % mod; } public int numWays(String[] a, String targ) { n = a.length; m = targ.length(); k = a[0].length(); freq = new long[26][k]; dp = new long[k + 1][m + 1]; for(int i = 0; i < n; i++){ String curr = a[i]; for(int j = 0; j < curr.length(); j++){ char ch = curr.charAt(j); freq[ch - 'a'][j]++; } } for(int i = 0; i Moving away from 2D array */ class Solution { public int numWays(String[] a, String targ) { int mod = (int)1e9 + 7; int n = a.length; int m = targ.length(); int k = a[0].length(); long[][] freq = new long[26][k]; long[] prev = new long[m + 1]; for(int i = 0; i < n; i++){ String curr = a[i]; for(int j = 0; j < curr.length(); j++){ char ch = curr.charAt(j); freq[ch - 'a'][j]++; } } prev[m] = 1; for(int idx = k - 1; idx >= 0; idx--){ long[] curr = new long[m + 1]; curr[m] = 1; for(int targIdx = m - 1; targIdx >= 0; targIdx--){ ---------------> TRIVIA long notpick = prev[targIdx] % mod; long pick = freq[targ.charAt(targIdx) - 'a'][idx] * (prev[targIdx + 1] % mod); curr[targIdx] = (notpick + pick) % mod; } prev = curr; } return (int)prev[0] % mod; } } TRIVIA > In the previous approach, we have used two 1D dp arrays ---> prev and curr. How to move from two 1D array to only one 1D array for space optimization? The inner loop(marked as TRIVIA) goes from m - 1 to 0. If i just write this loop ulta i.e. from 0 to < m it means same right? that is - for(int targIdx = 0; targIdx < m; targIdx++){ long notpick = prev[targIdx] % mod; long pick = freq[targ.charAt(targIdx) - 'a'][idx] * (prev[targIdx + 1] % mod); curr[targIdx] = (notpick + pick) % mod; } now how are we calculating curr[targIdx]. I sum up prev[targIdx] and prev[targIdx + 1] i.e. the idx just at the bottom and the idx at the right of it. So now if I overwrite the value at targIdx in the same prev[] array, it doesnt have any effect right bcz for suppose to fill up 0th index, i am using 0th index and 1st index and so on.Thats why we can completely eliminate curr array and keep only one 1D array which is the most optimal solution. /* SPACE OPTIMIZATION USING ONE 1D DP ARRAY */ class Solution { public int numWays(String[] a, String targ) { int mod = (int)1e9 + 7; int n = a.length; int m = targ.length(); int k = a[0].length(); long[][] freq = new long[26][k]; long[] prev = new long[m + 1]; for(int i = 0; i < n; i++){ String curr = a[i]; for(int j = 0; j < curr.length(); j++){ char ch = curr.charAt(j); freq[ch - 'a'][j]++; } } prev[m] = 1; for(int idx = k - 1; idx >= 0; idx--){ for(int targIdx = 0; targIdx < m; targIdx++){ long notpick = prev[targIdx] % mod; long pick = freq[targ.charAt(targIdx) - 'a'][idx] * (prev[targIdx + 1] % mod); prev[targIdx] = (notpick + pick) % mod; } } return (int)prev[0] % mod; } }

[@manishasaini307]

Bhaiya Awesome❤‍🔥

[@codestorywithMIK]

Thanks a lot Manisha 😊

[@jitDhank04]

Good morning sir 🌄

[@utkarsh-k6p]

Solved with just simple approach but got Tle . Frequency wala concept dimaag me hi nhi aayaa .. Your explanation is too good bhaiyaa . MY CODE -> class Solution { public: int MOD = 1e9 + 7 ; long long solve(int i,int j,vector& words, string target,vector&dp){ int n = words.size(); if(i == target.size()){ // we got our answer return 1; } if(j == words[0].size()){ return 0; } if(dp[i][j] != -1){ return dp[i][j]; } long long cnt = 0; for(int k = 0;k

[@tarasishbhattacharya1140]

Bhaiya you are doing great job. Can you cover some questions from dp and graph which asked in online rounds of top company

[@dhairyachauhan6622]

FOR THOSE WHO WANT TO DO IT THE NORMAL WAY(BUT IT GIVES TLE) EVEN WHEN MEMOIZED HENCE LISTERN TO HIS EXPLAINATION CAREFULLY class Solution { public: int mod = 1e9+7; vectordp; int solve(vector&words, string &target,int col,int idx){ if(idx == target.size()){ return 1; } if(col == words[0].size()){ return 0; } if(dp[col][idx]!= -1){ return dp[col][idx]; } int ans = 0; for(int row = 0;row

[@dhairyachauhan6622]

also bhiya the way you taught is very nice but is not intuitive ig (❁´◡`❁)

[@codestorywithMIK]

Really appreciate your input 🙏❤️😇

[@princechaurasia7624]

Thanks bro

[@codestorywithMIK]

Thanks for watching Prince ❤️❤️❤️

[@kunalkheeva]

GEnius!

[@codestorywithMIK]

Thanks a lot kunal

[@iWontFakeIt]

shukriya bhai

[@rajashreeparhi1549]

I've done dp but this ques was unique..i couldn't come up with solution..how can I improve myself??

[@tutuimam3381]

Thanks a lot

[@mehranahmed3612]

I am kind of confused by the recursive options. In distinctive subsequences Qs(Lc 115), when we only did the match operation when we had the matching string and i and j index but here you are using take option for every string and not even checking if they match or not. Is it because when the values are not matching you have a 0 value stored for them??

[@jewelchakraborty9717]

I approached this problem with this thought process. It may help you. Take the example of Mik's test case. The target is aba and the words are ['acca', 'abbb', 'caca']. I want to match the first character of target which is 'a'. Now when will 'a' match ? simply with the words which have 'a' as 1st character as you are thinking. Now, that's what we are getting from freq[][]. How many times does 'a' appear at 0th index across all words which is 2. From here only, the last word which is 'caca' gets ignored. I hope this clears you doubts. If not, please comment again. I will be happy to reply you back. Thanks.

[@mehranahmed3612]

@@jewelchakraborty9717 I got your point thanks. This problem kind of feels like that one only but is much harder

[@suryapratap2219]

@@mehranahmed3612 aise socho ki ab hum dictionary ko bhool gye aur mp use kar rhe aur map freq usee kar rhe aur usmein har col ke corresponding for all characters ya tof kuch pakka se freq hogi nhi to 0 hogi

[@tauheedahmed4073]

mazhar bhai apke github java sol mein do bhi same hai rec+memo and bottom up, ek bar verfiy karo and description ka hyper link dusre prob pe le ja raha hai

[@KishanSingh-vc3re]

class Solution { class Solution { public: int MOD = 1e9 + 7; int solve(int wi, int ti, vector& words, string& target, int n, vector& dp) { if (ti >= target.size()) { return 1; } if (wi >= words[0].size()) { return 0; } if (dp[wi][ti] != -1) { return dp[wi][ti]; } long long cnt = 0; for (int i = 0; i < n; i++) { if (words[i][wi] == target[ti]) { cnt++; } } long long take = (cnt * solve(wi + 1, ti + 1, words, target, n, dp)) % MOD; long long nottake = solve(wi + 1, ti, words, target, n, dp) % MOD; long long result = (take + nottake) % MOD; dp[wi][ti] = static_cast(result); return dp[wi][ti]; } int numWays(vector& words, string target) { int n = words.size(); int m = words[0].size(); vector dp(m + 1, vector(target.size() + 1, -1)); return solve(0, 0, words, target, n, dp); } }; why is this not working, anyone pls look into it, would be thankful

[@sauravfarkade1928]

class Solution { public: int md = 1e9 + 7; int targetLength = 0; int wordLength = 0; int solve(int ind, int t_ind, vector& words, string target, vector& dp) { if (t_ind >= targetLength) return 1; int cnt = 0; if (dp[ind][t_ind] != -1) return dp[ind][t_ind]; for (auto word : words) { for (int j = ind; j < wordLength; j++) { if (word[j] == target[t_ind]) cnt = (cnt + solve(j + 1, t_ind + 1, words, target, dp)) % md; } } return dp[ind][t_ind] = cnt; } int numWays(vector& words, string target) { int ind = 0, t_ind = 0; targetLength = target.length(); wordLength = words[0].length(); int n = words[0].size(), m = target.length(); vector dp(n + 1, vector(m + 1, -1)); return solve(ind, t_ind, words, target, dp); } }; I am getting TLE, even with memo

[@aws_handles]

Try passing target by reference

[@gurnoorchhabranit-jalandha5002]

Meko frequency wala logic samjh nhi aaya Agr kisi same index ke a pe wo target function na ban rha ho to kya hoga Lets say humare pass ab target hai And strings hai ["ab","ac"] is case me kya hoga

[@codestorywithMIK]

Hi Gurnoor, Can you explain this statement of yours : “Agr kisi same index k a pe wo target function na ban rha ho to kya hoga” May be then i can help clear

[@gurnoorchhabranit-jalandha5002]

@@codestorywithMIK like unable to understand the logic If we calculate the number of methods we can form target from a particular index lets say 0 Then we multiply with its number of frequency of that character on that particular index in other words But like what if its not possible to form.the word from the same index in another word Like we can form ab from 0th index of 2nd ab [ab,ab] But [ab,ac] we cant form ab from second word

[@codestorywithMIK]

I think i got your problem. The output is 2 for the example you gave above. Let me explain why : initially i = 0 and j = 0 Now, you have two options 1) Dont take this j -> answer 0 2) Take this j -> Here you have two options, either you can take ‘a’ of “ab” or ‘a’ of “ac” Now, let’s understand from tree diagram : 1) You took ‘a’ of “ab” (ab , ac) --> (b,c) Now you can choose ‘b’ and get one path which leads to answer 2) you took ‘a’ of “ac” (ab , ac) --> (b,c) Now you can choose ‘b’ and get one path which leads to answer So total 2 ways you get the answer.

[@JJ-tp2dd]

freq logic is to avoid making duplicate calls for the same state. In your example, lets say from words [ab, ac], you chose a of "ab". Next you will chose b of "ab". So 1 way. You could have also chosen a of "ac". And then chose b of "ab" to make the target, so answer is 1 from this side too. total answer is 2. Freq wle se you just find for one state and then multiply by 2 (freq of a at 0th index).

[@gurnoorchhabranit-jalandha5002]

@@codestorywithMIK thank you so much for this And one more doubt how did we insure that when we took the element from jth string it matches with the element of ith string

[@gui-codes]

Recursion + Memoization : ❌ Khandani Approach : ✅ Hard to ko Halwa banadiya

[@India_mera_sabkuch]

bhai likh ke deta hun itni asani se dsa samjhane vala teacher to aaj tak paid courses me nhidekha

[@gui-codes]

@@India_mera_sabkuch true bhai

[@vaibhavkumargautam]

khandaANI TARIKA 🤣🤣 . AWESOME THUMBNAIL🤣🤣

[@abhiverma5135]

according to que we can pick two characters from same word so why are you doing i + 1 in taken recursive call?

[@032_RishavDey]

Mine is giving negative answer for a few test cases in java. Can someone help me with this!!!!

[@codestorywithMIK]

Kindly share your java code

[@032_RishavDey]

@@codestorywithMIK The problem was occurring due to integer overflow. It got resolved. I took long everywhere and type casted it to int at the end.

[@JJ-tp2dd]

Java Solution: class Solution { private int m; private int k; private int dp[][]; private int mod; private int solve(long freq[][], String target, int i, int j) { if(i == m) return 1; if(j == k) return 0; if(dp[i][j] != -1) return dp[i][j]; long notTaken = solve(freq,target,i,j+1) % mod; long taken = (freq[target.charAt(i)-'a'][j] * solve(freq,target,i+1,j+1)) % mod; return dp[i][j] = (int)((notTaken + taken) % mod); } public int numWays(String[] words, String target) { this.m = target.length(); this.k = words[0].length(); this.mod = 1000000007; this.dp = new int[1001][1001]; for(int[] d : dp) Arrays.fill(d,-1); long freq[][] = new long[26][k]; for(int col=0; col

[@doomhead9109]

what is the significance of checking i == m before the j == k in the base case ?

[@codestorywithMIK]

Let’s say j reached k and at the same time i also reached m Example : target = “abc” Words = {“axy”, “xbz”, “hdc”} If you check j == k first you will think that every column (index) is over and you didnt get your target but at the same time i == m also reached which will be missed. So it’s better to check that if i reached m, it definitely means all characters of target are found.

[@doomhead9109]

@@codestorywithMIK Got it Sir Thank you sooo much.

[@mathematics7746]

humlog pick wala case me tabhi jayenge jab target[j] appear kr rha hoga os column me tabhi call karenge but ap hamesa call kr rhe hai can you explain this why?

[@codestorywithMIK]

Hi, actually if you notice we are multiplying with frequency of the character in that index from freq table. if a character has no frequency in jth index then it will anyways be 0 because we are multiplying the frequency.

[@mathematics7746]

Yes got it thanks

[@psychologyfact2320]

Thanks🙏

[@AftabAlam-gh1nh]

public int helper(String[] words,String target,int i,int j){ if(j==target.length())return 1; if(i>=words[0].length())return 0; int ans=0; for(int k=0;k

[@KeshavKumar-jl1ub]

leetcode solution of github link and leetcode link is wrong sir

[@codestorywithMIK]

Corrected. Thank you for pointing 😇🙏

[@KeshavKumar-jl1ub]

@@codestorywithMIK sir you told that u ll upload the solution of contest... if possible please upload... i know its not easy always... a person have many jobs.. although we thankful to yo u for this only. no problem if its not possible..

[@aadil4236]

Umm, Mik the link to the code on github is incorrect. It takes us to the yesterday's challange.

[@codestorywithMIK]

It’s corrected now. Thank you for pointing it out ❤️

[@manimanohar_001]

Remainder: leetcode 1171 and 92

[@codestorywithMIK]

One Coming today 🙌😊

[@manimanohar_001]

@@codestorywithMIK still I'm awake for that one haunting video.

[@aizad786iqbal]

Hey u pasted same code in java FOR recur memo also I wrote java code based on your c++ code , although had to figure out later it should be long class Solution { int solve(int i, int j, long[][] freq, String target, long[][] dp) { if(i == target.length()){ return 1; } if(j == freq[0].length){ return 0; } if(dp[i][j] != -1){ return (int)dp[i][j]; } long MOD = (long)1e9+7; long not_taken = solve(i, j+1, freq, target, dp) % MOD; long taken = (freq[target.charAt(i) - 'a'][j] * solve(i+1, j+1, freq, target, dp)) % MOD; dp[i][j] = (not_taken + taken) % MOD; return (int)dp[i][j]; } public int numWays(String[] words, String target) { int k = words[0].length(); int m = target.length(); long[][] freq = new long[26][k]; long[][] dp = new long[m+1][k+1]; for(int col = 0; col < k; col++) { for(String word : words) { char ch = word.charAt(col); freq[ch - 'a'][col]++; } } for(long[] x : dp){ Arrays.fill(x, -1); } return solve(0, 0, freq, target, dp); } }

[@codestorywithMIK]

Thank you for pointing this out. I usually travel during weekends and hence missed this in rush ❤️🙏

[@AtulBhadouriya-m8s]

why this is giving me memory limit exceeded class Solution { public: int m,k; const int MOD = 1e9+7; int solve(int i,int j,vector &freq,string &target,vector &t){ if(i == m){ return 1; } if(j == k){ return 0; } if(t[i][j] != -1){ return t[i][j]; } int not_taken = solve(i,j+1,freq,target,t)%MOD; int taken = (freq[target[i]-'a'][j]*solve(i+1,j+1,freq,target,t))%MOD; return t[i][j] = (taken+not_taken)%MOD; } int numWays(vector& words, string target) { m = target.size(); k = words[0].size(); vector freq(26,vector (k)); for(int col=0;col

[@harjotanand834]

Hello sir , did this code on my code top down approach but is giving TLE in last 7 testcase ....can you please tell the problem in the code ....ThankYou Sir 🙏🏼🙏 #define mod 1000000007 class Solution { public: int t[1009][1009]; int solve(vector& words , string target , int k , int i){ if(k == words[0].length() && i == target.length()){ return 1; } if(k == words[0].length() && i < target.length()){ return 0; } if(t[k][i] != -1){ return t[k][i]; } long long answer = 0; for(int j = 0 ; j < words.size() ; j++){ char ch = words[j][k]; if(ch == target[i]){ answer += solve(words,target,k+1,i+1)%1000000007; } } answer += solve(words,target,k+1,i)%mod; return t[k][i] = answer%mod; } int numWays(vector& words, string target) { memset(t,-1,sizeof(t)); return solve(words,target,0,0); } };

[@harjotanand834]

Ohh ...realised since I included a for loop ...Its TC gone to O(n³)

[@atifhu]

same approach is temporary.......khandani tareeka is permanent.🤣

[@codestorywithMIK]

❤️😊

[@androiddude1296]

I was getting some error for the taken part runtime error: signed integer overflow: 10 * 238549204 cannot be represented in type 'int' (solution.cpp) SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior prog_joined.cpp:24:43 so i used this and now i am getting memory limit exceeded 😶 int t = (1LL * freq[target[i] - 'a'][j] * solve(i + 1, j + 1, k, freq, target)) % mod;

[@androiddude1296]

class Solution { public: const int mod=1e9+7; int m[1001][1001]; int solve(int i,int j,int k,vector& freq, string target){ if(i==target.length()){ return 1; } if(j>=k){ return 0; } if(m[i][j]!=-1){ return m[i][j]; } int t = (1LL*freq[target[i] - 'a'][j] * solve(i + 1, j + 1, k, freq, target)%mod) % mod; int nt=solve(i,j+1,k,freq,target)%mod; return m[i][j]=(t+nt)%mod; } int numWays(vector& words, string target) { int n=words.size(); int k=words[0].length(); memset(m,-1,sizeof(m)); vector freq(26,vector(k,0)); for(int i=0;i

[@ansh6552]

Pass string with reference and it will pass all test cases

[@androiddude1296]

@@ansh6552 Ok i'll try thank you