Good video! But I think it's better to not set the out variable as you go through the matrix. On two large strings, that could waste a lot of time allocating memory.
Hello Sam, Thanks for the video series. Just a small request- would it be possible to categorize or tag the problems in types such as DP, Strings, graphs, trees, etc. either on your website or on your CZcams. That will be really helpful.
You're welcome! And if you go on the website, they are tagged. See the links to different categories here: www.byte-by-byte.com/coding-interview-questions/
Kind of a nitpick here.... I added a variable: int len = 0; Then assigned the value to the cache like so: cache[i][j] = len = cache[i-1][j-1] + 1; Here's the nitpick: When I save the current longest String I used: out = a.substring(i - (len-1), i+1); I think it makes more sense, and is less confusing than subtracting and then adding back. (i - cache[i][j] + 1)
I get the general idea here, but haven't been able to make this code work. I think the disconnect has to do with the a.substring(i - ?? + 1, i + 1) bit you changed at the end, and I'm sure there's some combination of variables and operators that make it actually work, but haven't been able to work out what those might be yet. I tried the various things mentioned in the video, and various permutations thereof, but haven't figured it out yet. When debugging, it quickly becomes a sea of variables of ABA BABA ABAB A and 1's and 2's and 3's...
Your solution produces a Time and Space complexity of 0(nm), is there any particular reason why you chose to create a NxM matrix? I think this can be done in O(1) space?
Yeah usually as you improve the time complexity, you make the space complexity worse and vice versa. The extreme example is that any problem can be solved in constant time if you save the output for every possible input
good video until you changed the substring function at the very end. little more explanation would have helped coz that is the most imp part and a bit confusing as well
cache[i][j] is the length of the common substring, i is the index of the last character in the substring. Therefore, (i - cache[i][j] + 1) is the index of the first character in the common substring, which is exactly what we need for a substring function.
Byte By Byte Oh I was doing it in c++. i could follow entire syntax was c++ knowledge . never looked into java. I've an interview this Monday so was particular about it so that I don't type it wrong. thank you very much for your response and video :)
Byte By Byte yea even c++ has new to create something on heap although I suspect it should be int cache [ ][ ]= but not int [ ][ ] cache=. good to know the difference though :)
Using a sliding window approach would offer the same O(a * b) complexity and is much simpler than DP? Here are two examples: imgur.com/a/FHncMsn imgur.com/a/mlRRMeF
Thanks for the video but please rehearse your talking script before recording. The explanation feels like completely disjointed, confusing and honestly full of mistakes.
for input strings a = "stone", b = "longest" the output would come here as "st" of length 2 which would be wrong. The correct answer would be "one" of length 3. Hence, you should add else case - if a.charAt(i) != b.charAt(j) cache[i][j] = Math.max(cache[i-1][j], cache[i],[j-1])
omg
this video needs to be remade. The whole time I was confused with the i - length + 1, which is actually i - cache[i][j] + 1.
exactly what I thought
the way it is explained it very confusing.
It's basically edit distance. Checkout out back to back swe's explanation of edit distance and then keep this in mind.
At 13:30 totally agree it’s easier to do 2d array first then optimize to 1d if there’s enough time leftover
Your channel is a gem, Thanks for all the stuff.
Good video! But I think it's better to not set the out variable as you go through the matrix. On two large strings, that could waste a lot of time allocating memory.
Think you got the i and j mixed up while testing?
That's totally possible, but it's fine as long as the code is consistent
a more optimized solution exists for this question with constant space complexity. The idea is to expand around the centers.
Hello Sam,
Thanks for the video series. Just a small request- would it be possible to categorize or tag the problems in types such as DP, Strings, graphs, trees, etc. either on your website or on your CZcams. That will be really helpful.
You're welcome!
And if you go on the website, they are tagged. See the links to different categories here: www.byte-by-byte.com/coding-interview-questions/
Thanks!
Kind of a nitpick here....
I added a variable: int len = 0;
Then assigned the value to the cache like so: cache[i][j] = len = cache[i-1][j-1] + 1;
Here's the nitpick: When I save the current longest String I used: out = a.substring(i - (len-1), i+1);
I think it makes more sense, and is less confusing than subtracting and then adding back. (i - cache[i][j] + 1)
Not personally a fan, but this just goes to show that everyone has their own coding style and one isn't necessarily better than the other :)
what if the strings are of different sizes, would this still work?
If we have "ABCA" and "BCA" then you need to do if (cash[i][j] >= out.length()).
i like it very much thankyou keep helping us ...
I get the general idea here, but haven't been able to make this code work. I think the disconnect has to do with the a.substring(i - ?? + 1, i + 1) bit you changed at the end, and I'm sure there's some combination of variables and operators that make it actually work, but haven't been able to work out what those might be yet. I tried the various things mentioned in the video, and various permutations thereof, but haven't figured it out yet. When debugging, it quickly becomes a sea of variables of ABA BABA ABAB A and 1's and 2's and 3's...
When you calculate a.substring(i - length + 1, i + 1), the length is the length of the out string variable, correct?
yeah I think that's right
i think you're correct,
24 minutes to provide the answer?
Thanks for great explanation!! Best one on DP prob ..
you're welcome!
Understand properly and it’s great algorithm and vedio as well. I was thinking how it can be possible with singleArray(n+m) length ?
What would be the complexity of the trie solution?
Your solution produces a Time and Space complexity of 0(nm), is there any particular reason why you chose to create a NxM matrix? I think this can be done in O(1) space?
Actually, nvm. I think to get to constant space, the time complexity would go up to O(nm^2)
actually wait, i think i double wronged myself. I believe this -can- be done with O(nm) Time and O(1) Space
Yeah usually as you improve the time complexity, you make the space complexity worse and vice versa. The extreme example is that any problem can be solved in constant time if you save the output for every possible input
@@ByteByByte Youre Wrong For saving that output you most to compute the result Genius !
i think you missed the most important part - the time and space complexity analysis????
good video until you changed the substring function at the very end. little more explanation would have helped coz that is the most imp part and a bit confusing as well
Anything I can clarify now?
Great explanation, But I could not understand how you put i-cache[i][j]+1
cache[i][j] is the length of the common substring, i is the index of the last character in the substring. Therefore, (i - cache[i][j] + 1) is the index of the first character in the common substring, which is exactly what we need for a substring function.
Sorry just wondering if it would be a.substr or a.substring?
docs.oracle.com/javase/7/docs/api/java/lang/String.html#substring(int,%20int)
Byte By Byte Oh I was doing it in c++. i could follow entire syntax was c++ knowledge . never looked into java. I've an interview this Monday so was particular about it so that I don't type it wrong. thank you very much for your response and video :)
Ah yeah. Its good how similar the languages are because these solutions can still be helpful, but I can see why it might get a little confusing
Byte By Byte yea even c++ has new to create something on heap although I suspect it should be int cache [ ][ ]= but not int [ ][ ] cache=. good to know the difference though :)
What's the runtime and space complexity?
O(a*b)
length variable??
what is length variable?
Using a sliding window approach would offer the same O(a * b) complexity and is much simpler than DP? Here are two examples: imgur.com/a/FHncMsn imgur.com/a/mlRRMeF
forget the interview and interviewer man.
just focus on the concept
Thanks for the video but please rehearse your talking script before recording. The explanation feels like completely disjointed, confusing and honestly full of mistakes.
for input strings a = "stone", b = "longest" the output would come here as "st" of length 2 which would be wrong. The correct answer would be "one" of length 3. Hence, you should add else case - if a.charAt(i) != b.charAt(j) cache[i][j] = Math.max(cache[i-1][j], cache[i],[j-1])
This question is about longest common substring, not longest common sequence.