small optimisation: declare curr string outside the loop to avoid using substr function.. and keep adding characters to curr as we iterate in the inner loop.
can I also use kmp algorithm? I will create a visited array initialised to 0 and have length equal to length of given string . now using Kmp , we can know which index is visited by every substring. after that we count number of 0's in visited array . this approach will take only N*K time complexity . where K is length of array.
The substring is being created here string curr = s.substr(i, j-i+1); i is the starting index and the length of the substring from i to j will be j-i+1
I've done in greedy approach but got WA in test case 1994. But still I'm confuse what's wrong with my approach. However can anyone tell me dp/recusion is the only way to solve this problem? Greedy approach won't work?
I had done similar to you , but after analysing my solution i knew my mistake... Basically I was finding the largest substring on any index that is present in dictionary and then moving to the end of substring but this approach is wrong because there is a possibility that a smaller substring might eventually have a longer substring.... PS-I haven't studied DP till now
i like the way of converting code in bottom up, but i can't understand the what to use 0...n or n....0 now. are both same? in every situation. pls stick to one way only
Bhai bottom up. Ke jaruri hai uska state definition that is while memorizing what are u storing in each cell of used data structure for memoization....
Hi , In my java code I was getting an error , class Solution { public int minExtraChar(String s, String[] dictionary) { HashSet set = new HashSet(); int n = s.length(); for(String str : dictionary){ set.add(str); } return solve(0 , s , set , n); } public int solve(int i , String s , HashSet set , int len){ if(i >= len){ return 0; } int res = 1 + solve(i + 1 , s , set , len); for(int j = i ; j < len ; j++){ String cur = s.substring(i , j - i+ 1); if(set.contains(cur)){ res = Math.min(res , solve(j + 1, s , set , len)); } } return res; } } When I did String cur = s.substring(i , j - i+ 1); I got and error but when I used String cur = s.substring(i , j + 1); , it ran successfully. Why is there a difference in this Java code and your C++ code?
In C++, substr is a member function of the std::string class that extracts a substring by specifying a starting position and an optional length. In Java, substring is a method of the String class, and you provide the start and end indices (end is exclusive). The key difference is that C++ allows you to specify the length of the substring, while Java requires both start and end indices for extracting the substring.
i have done by trie and dp saw your trie video. class Node{ Node[]child; boolean isEnd; public(){ child=New node[26]; isEnd =false; } } class Solution { public int minExtraChar(String s,String[]dict){ Node root=new Node(); for(String t:dict){ insert(t,root); } int n=s.length(); int[]dp=new int[n+1]; for(int i=0;i
The way you explain problems makes even hard ones feel easy. Thank you so much.
small optimisation: declare curr string outside the loop to avoid using substr function.. and keep adding characters to curr as we iterate in the inner loop.
Yaar aapne DP, Graph, Trie ka dar bhaga diya hai ❤❤❤
इसी वीडियो का इंतेजार कर रहे थे.❤
Yaar aap kitna sahi parhate ho. Literally I love your voice
I really like your videos, I would recommend to do codeforces problems or contests solutions as well that is real problem solving.
thank you 🥰 very much I am still doing POTD in my mid sem exam
Thank you so much Bhaiya ji 🙏🙏🙏
Radhe Radhe sir ji
Radhe Radhe ❤️😇
Radhe Radhe
Radhe Radhe 😇❤️🙏
who is come directly on this video
me
@@gui-codesyou is English very nice
@@Code_loadingHe in is a university 😅
Me too
Thanks a lot bhaiya ❤❤
Most welcome ❤️😇
can I also use kmp algorithm?
I will create a visited array initialised to 0 and have length equal to length of given string . now using Kmp , we can know which index is visited by every substring. after that we count number of 0's in visited array . this approach will take only N*K time complexity . where K is length of array.
Thanks a lot
Thank You Bhaiya (Red Heart)
Sir sirf memoization wale ka time complexity kya hoga n cube?
how do i think of the reverse iteration in the top down approach, i understoodd it, but unable to click
please help sir
Pls make video on trie approach
Shooting this early morning..mik bhaiya ?
Yes i mostly record early morning.
Least disturbance 😇❤️
@@codestorywithMIK can you suggest any coding sheet my OA and interviews are in some days
Why do we do take not take here when we can do all the things inside for loop like your other video?
Can you please suggest which Tab and which app are you using to make videos?
It’s ipad 11 pro.
And i use the default app in it - Notes
Hope that helps ❤️
Bhaiya aap bhi please ek DSA sheet bnadijiye pleasee
I was trying to use trie and in the process i messed up the code and got to incorrect answer..
bottom up approach me substring kese create ho rha hai mtlb, last to start, iam not getting it
The substring is being created here
string curr = s.substr(i, j-i+1);
i is the starting index and the length of the substring from i to j will be j-i+1
I've done in greedy approach but got WA in test case 1994. But still I'm confuse what's wrong with my approach. However can anyone tell me dp/recusion is the only way to solve this problem? Greedy approach won't work?
I had done similar to you , but after analysing my solution i knew my mistake... Basically I was finding the largest substring on any index that is present in dictionary and then moving to the end of substring but this approach is wrong because there is a possibility that a smaller substring might eventually have a longer substring....
PS-I haven't studied DP till now
i like the way of converting code in bottom up, but i can't understand the what to use
0...n or n....0 now. are both same? in every situation. pls stick to one way only
Ye dp itni hard kyu h🥹 ..can we always derive bottom up from top down ???? Please help❤😊
Yes its always possible, but in some problems it can be tricky.
Bhai bottom up. Ke jaruri hai uska state definition that is while memorizing what are u storing in each cell of used data structure for memoization....
aaj pehli bar na question samjha aur na solution..
bhai itna sahi to samjhaya hai. classic dp problem hai
but your old code was diff, usme toh ham for loop ke andar skip waala condition likhte they
We can do in both ways .
Multiple ways to solve a problem
present
iterative khud krlia, just recursion sochne mai time lgta
❤️👍🏻
Hi , In my java code I was getting an error ,
class Solution {
public int minExtraChar(String s, String[] dictionary) {
HashSet set = new HashSet();
int n = s.length();
for(String str : dictionary){
set.add(str);
}
return solve(0 , s , set , n);
}
public int solve(int i , String s , HashSet set , int len){
if(i >= len){
return 0;
}
int res = 1 + solve(i + 1 , s , set , len);
for(int j = i ; j < len ; j++){
String cur = s.substring(i , j - i+ 1);
if(set.contains(cur)){
res = Math.min(res , solve(j + 1, s , set , len));
}
}
return res;
}
}
When I did
String cur = s.substring(i , j - i+ 1); I got and error but when I used
String cur = s.substring(i , j + 1); , it ran successfully.
Why is there a difference in this Java code and your C++ code?
In C++, substr is a member function of the std::string class that extracts a substring by specifying a starting position and an optional length. In Java, substring is a method of the String class, and you provide the start and end indices (end is exclusive). The key difference is that C++ allows you to specify the length of the substring, while Java requires both start and end indices for extracting the substring.
@@codestorywithMIK ok lord , got it
Thanks for the explanation!
❤️🙏 Most welcome
i have done by trie and dp saw your trie video.
class Node{
Node[]child;
boolean isEnd;
public(){
child=New node[26];
isEnd =false;
}
}
class Solution {
public int minExtraChar(String s,String[]dict){
Node root=new Node();
for(String t:dict){
insert(t,root);
}
int n=s.length();
int[]dp=new int[n+1];
for(int i=0;i
Awesome ❤️