Extra Characters in a String | Tree Diagram | Recursion | Memoization | MADE EASY | Leetcode - 2707

[@codestorywithMIK]

Bottom Up - kzbin.info/www/bejne/bp2aZ3mfgtaMfsksi=GO09KZIASjrhh3ib Thank you ❤

[@sauravchandra10]

Was able to pass 2006 cases on my own. Came to your solution, figured it would be similar to word break and then was able to code it up on my own. Now to bhaiya's story.

[@UtkarshPatel-v9o]

nice explanation bhaiya

[@codestorywithMIK]

Thank you 😇❤️

[@anuppatankar4294]

Great Video 👌🏻

[@codestorywithMIK]

Thank you Anup 😇❤️

[@mohithadiyal6083]

The best explanation

[@reshusingh3558]

thank you sir

[@abhishek__anand__]

Great Explanation

[@rohan8758]

Good explanation but given code is different from explained in the video. But thanks for the approach & new code both Mike!!!

[@codestorywithMIK]

Most welcome ❤️😇🙏

[@sunilsarode152]

many thanks to you, I was not sure about my tree and then saw your and then I coded it and it works :)

[@dhairyachauhan6622]

Todays question was a cakewalk :) , Those who were not able to do dont worry it was easy for me after 120 dp questions :p

[@codestorywithMIK]

Dope 🔥🔥💪💪

[@rounaq_khandelwal]

glad to re-connect with this lovely channel!! I hope ab na break ho streak isse dekhne ki ;) Keep up the work mic bhai! I remember apne similar sa qn pehli kuch videos m kraya tha toh was able to code this up after listening to the story!

[@rounaq_khandelwal]

(note- we have to use push_back instead of substr() function in this question) class Solution { int dp[51]; int f(string &s,unordered_set& dict,int i){ if(i>=s.size()) return 0; if(dp[i]!=-1) return dp[i]; int minAns=s.size(); for(int j=i;j

[@codestorywithMIK]

So glad to hear that. Thank you 😇❤️🙏

[@saurabhtiwari9614]

My approach - I have count max length of all the subarray present in dictionary. And then subtract the length with total length of string.

[@shivamtomar9658]

thanks sir❤

[@vivekkumaryadav9862]

Thnanks sir ,,

[@ugcwithaddi]

You are the best ❤

[@wearevacationuncoverers]

exceptional explanation. I wonder how easy the code becomes when we first draw the tree diagram. it's amazing

[@vaibhavgupta973]

thank you

[@codestorywithMIK]

Thanks to YOU for watching ❤️❤️

[@AlishaKhan-ww3io]

wonderful explanation as always. I was able to solve it using your previous teachings. Thank you so much for improving me

[@_AmanKumar_CSD]

Osumn Explanation bhaiya 🥰🥰❤❤!! Thank you for the content Like This Video ,,,, !!

[@aman3210]

thankyou

[@codestorywithMIK]

You're welcome! ❤️

[@ravitejasriram4284]

Java Code: class Solution { int n; int[] dp; public int minExtraChar(String s, String[] dictionary) { n = s.length(); dp = new int[n]; Arrays.fill(dp, -1); Set set = new HashSet(); for(String s1 : dictionary) { set.add(s1); } return solve(s, set, 0); } public int solve(String s, Set set, int in) { if(in >= n) return 0; if(dp[in] != -1) return dp[in]; int minChars = n; for(int i=in;i

[@Tanyyaa_13]

Thanks for uploading the video early in the morning🙏🙏. I was just going through the question and saw you uploaded the video😅😁

[@CodeBoost8375]

I solved this question myself but i come to see your story . To know better about the solution.

[@codestorywithMIK]

It means a lot to me. Thanks for watching. And super proud that you solved it on your own 💪💪💪

[@CodeBoost8375]

@@codestorywithMIK thanks bro or ek or cheej puchna tha wo digit dp par video kab laoge ?

[@codestorywithMIK]

@ashokasamrat8375 Actually in my DP concepts playlist, i am planning to go step by step. Once i cover 1D Dp, 2D Dp, String based DP, then it would be good to finally jump to advanced topics like Digit Dp etc.

[@CodeBoost8375]

@@codestorywithMIK ohh ok thanks

[@muditkhanna8164]

Please make a video on easy conversion of memoization to tabulation dp.

[@souravjoshi2293]

tree diagram almost tells what the code will look like ❣❣❣❣

[@codestorywithMIK]

True

[@vineetkumarmotwani474]

My implementation (bottom up) : class Solution { public: int minExtraChar(string s, vector& dict) { int n = s.length(); int dp[n+1]; dp[0] = 0; // Min ele required to erase at that index unordered_set dictSet(dict.begin(), dict.end()); for (int i = 1; i = 1; j--) { string word = s.substr(j-1, i-j+1); if (dictSet.count(word)) dp[i] = min(dp[i], dp[j-1]); } } for(int i=0; i

[@codestorywithMIK]

Awesome 👌

[@ganeshmula4508]

🤯🤯🤯🥳

[@codeandtalk6]

❤❤❤

[@dayashankarlakhotia4943]

class solution { Public int min Extra (string s,string []dictionary){ setdict=new Hash set (Array. as list (dictionary)); int []dp=new int [s.length +1]; Array. fill (dp,-1); return solve (0,dict,s,dp); } Public int solve (int idx,Hash set dict,string s,int []dp){ if(idx>=s.length ()){ return 0; } int min=(int)(1e9); if(dp[idx]!=-1){ return dp[idx]; } for(int i=idx;i

[@rpdesigns3545]

excellent explanation sir

[@codestorywithMIK]

Thanks a lot ☺

[@souravkumar7612]

socha tha map se khud kar loonga ,at last wapas aaya after failing test case 313😅

[@SanskarGarg]

I solved it in way that you solved Word Break Problem previously. class Solution { public: unordered_map mp; int dp[51]; int f(int indx , string &str){ if(indx >= str.size()) return 0; if(dp[indx] != -1) return dp[indx]; int ans = INT_MAX; for(int len =1 ; len

[@codestorywithMIK]

Awesome. 💪💪 I forgot to mention this. Indeed this is similar to word break ❤️❤️

[@top_g755]

Sir for loop ke andar nai string bna kar check krne ke jgh directly set.contains(s.substring(i,idx)) nhi likh skte if not then i-1 add krdenge min extra mei

[@codestorywithMIK]

You can. But calling substring is costly (takes O(n) time in worst case))

[@nidhimishra2436]

Bro Plz.. start with GFG POTD as well it will be great Help !

[@akki8534]

Leetcode is best Bro

[@bytecoding9685]

java tabulation solution class Solution { Integer dp[]; public int minExtraChar(String s, String[] dictionary) { HashSet stringSet = new HashSet(); for(String word:dictionary){ stringSet.add(word); } dp = new Integer[s.length()+1]; dp[s.length()]=0; for(int i=s.length()-1;i>=0;i--){ int min = s.length()-i; for(int j=i;j

[@dhairyachauhan6622]

Also bhiya i wanted to ask how does one understand someone else solution. I mean the solution on solution tab do you just dry run on them? I find dry running on someone else solution very much time consuming. So how do i deal with it.

[@codestorywithMIK]

Actually in the beginning i used to do dry run. But with time as your understanding gets better and better you no longer will have to do dry run line by line.

[@Tejaswi-xd4re]

Sir when will post the question list video?

[@codestorywithMIK]

Hey 👋 Actually i am travelling, i will plan it soon.

[@Tejaswi-xd4re]

@@codestorywithMIK ok sir np enjoyy...

[@codestorywithMIK]

@Tejaswi-xd4re Thank you brother for understanding ❤️❤️❤️

[@Vipulghadi]

sir tabulation wala aproach kha milega

[@gui-codes]

waiting for Bottom Up today (watching it on 23rd Sept - POTD)

[@codestorywithMIK]

kzbin.info/www/bejne/bp2aZ3mfgtaMfsksi=GO09KZIASjrhh3ib

[@39_jatinjain4]

little bit confusion is still there like every time new currstr andat returning time it pushes another char

[@codestorywithMIK]

Hi Jatin, Thank you for sharing your concern. I would suggest you to do a dry run on a very small example. s = “abd “ {“a” , “d”} I am sure this will help

[@doomhead9109]

github code does not contains the memoization part

[@codestorywithMIK]

Thanks a lot. I have updated it ❤️❤️

[@thekindspill]

Wowww. Early morning. Pakka bhai travel karne ja rahe kya ? 😅 Thanks btw ❣

[@BenJasper-u2x]

Nothing But bhai can you just tell me from when you will start Graph and trees videos addition Thanks

[@codestorywithMIK]

Hi there, Do you mean Graph Playlist ? It’s already there in my playlist 1) Graph Popular Interview Qns - kzbin.info/aero/PLpIkg8OmuX-I_49pdy1XFY6OcATnxUrrO&si=HkNaJvN1KgxU5o6N 2) Graph Concepts Playlist - kzbin.info/aero/PLpIkg8OmuX-LZB9jYzbbZchk277H5CbdY&si=GjFDHvH9BaND8zPS Similarly I will be creating Tree Concepts as well soon.

[@BenJasper-u2x]

@@codestorywithMIK can u just add more videos to that playlist of graph bhai thats all

[@yagamilight1690]

I am not able to memoize following , I thought of approach of take nottake class Solution { public: unordered_mapmp; int dfs(int curr , int n ,string &s, vector& dictionary , string temp) { if(curr == n) return 0 ; string str = temp + s[curr]; int take = 0 ; if(mp.count(str) > 0) { take = str.size() + dfs(curr+1,n,s,dictionary,""); } take = max(take, dfs(curr+1,n,s,dictionary,str)); int notTake = dfs(curr+1,n,s,dictionary,""); return max(take,notTake); } int minExtraChar(string s, vector& dictionary) { for(auto &word:dictionary) { mp[word] += 1; } int n = s.size(); string temp = ""; return n - dfs(0,n,s,dictionary,temp); } };

[@M.m554]

Sir plz tell the ans of this ques.. is null palindrome or not justify.

[@codestorywithMIK]

Yes, a null string (an empty string) is considered a palindrome. A palindrome is a word, phrase, number, or other sequence of characters that reads the same forward and backward. Since an empty string doesn't contain any characters, it satisfies the condition of reading the same forward and backward, as there are no characters to reverse. Therefore, it can be considered a palindrome by definition.

[@M.m554]

@@codestorywithMIK thankyoouu sir

[@taneyasoni]

2/30

[@codestorywithMIK]

Let’s go 🔥🔥🔥

[@prudhvirajmacherla9854]

plz explain in english as well as plz post the respective java code

[@codestorywithMIK]

Hello there, I will try to put different videos for English version of my videos. It might take time but I will soon plan it . ❣❣❣ Please find the JAVA code below (also added in my Github Link in Description) class Solution { int n; int[] t; public int minExtraChar(String s, String[] dictionary) { n = s.length(); t = new int[n]; Arrays.fill(t, -1); Set set = new HashSet(); for(String s1 : dictionary) { set.add(s1); } return solve(s, set, 0); } public int solve(String s, Set set, int idx) { if(idx >= n) return 0; if(t[idx] != -1) return t[idx]; int minChars = n; for(int i = idx; i < n; i++) { String temp = s.substring(idx, i+1); if(set.contains(temp)) { minChars = Math.min(minChars, solve(s, set, i+1)); } else { minChars = Math.min(minChars, temp.length() + solve(s, set, i+1)); } } return t[idx] = minChars; } }

[@rubellite5766]

Sarre question galat marked hein, "Hard marked he but bahut easy he", "Medium marked he but bahut hin jyada easy he" 💀💀💀💀

[@codestorywithMIK]

🤓🤓🤓

[@crosswalker45]

nhi smja ye problem🥲

[@codestorywithMIK]

Hi there, sorry to hear that. Would you please mention where exactly you lost the explanation ? I will try my best here to explain more 😇🙏❤️

[@twitterstreet1959]

thank you

[@tutuimam3381]

❤❤❤