I came across some other popular videos explaining this problem, and this is so far the most favorite video which contain the explanation that I am looking for. Thanks alot
Amazing explanation of the problem statement and the solution! We had this question in lecture last week and I found it really confusing, thanks for helping out with this Nikhil!!
class Solution { public int longestCommonSubsequence(String text1, String text2) { // Ensure text1 is the longer string to minimize space usage if (text2.length() > text1.length()) { return longestCommonSubsequence(text2, text1); } // Convert strings to character arrays for easy access char[] s1 = text1.toCharArray(); char[] s2 = text2.toCharArray(); // Create two arrays to store the lengths of longest common subsequences int[] previousRow = new int[s2.length + 1]; int[] currentRow = new int[s2.length + 1]; // Loop through each character in s1 for (int i = 0; i < s1.length; i++) { // Loop through each character in s2 for (int j = 0; j < s2.length; j++) { // If characters match, increment the length from the previous row and previous column if (s1[i] == s2[j]) { currentRow[j + 1] = previousRow[j] + 1; } else { // If characters don't match, take the maximum length by ignoring one character either from s1 or s2 currentRow[j + 1] = Math.max(currentRow[j], previousRow[j + 1]); } } // Swap rows: currentRow becomes previousRow for the next iteration int[] temp = previousRow; previousRow = currentRow; currentRow = temp; } // The length of the longest common subsequence is in the last element of previousRow return previousRow[s2.length]; } public static void main(String[] args) { Solution solution = new Solution(); // Test cases System.out.println(solution.longestCommonSubsequence("abcde", "ace")); // Output: 3 System.out.println(solution.longestCommonSubsequence("abc", "abc")); // Output: 3 System.out.println(solution.longestCommonSubsequence("abc", "def")); // Output: 0 } } this is true dynamic solution
Hello Sir, can you make a good video about iteration and loops ? And I hope you will not give the example " You need to repeat 10 times hello, how would you do it ? " ..
@@nikoo28 I dont even know what i'm trying to understand .. I solved 380 problems on LeetCode and still can't really understand them a hundred percent, I use for and while loops to solve problems by pure instinct .. It's like these loops are simulating real world but at a text level , for example if i want to drink a glass of water the translation to text is while ( i still have water in the glass) i keep doing the drinking logic and decrease the water in the glass, but then you have conditions like while (i still have the light on) i keep reading , but that condition is changing based on something decreasing or increasing because mathematics is present in everything right ? we can quantify everything if we really think about it no ? I'm trrying to create this clear picture in my mind comparing programming text and real life and real life to programming text .. Am i overthinking this or I am going crazy ? Please help Sir !
@@exe.m1dn1ght I never imagined a way of comparison like this. I think you should start making videos of how are you relating with real life. A different perspective which will be very cool to know
@@ankurbassi2667 i had a very wrong perspective about this, i figured out its just instructions, like the ones you read on a cooking recipe. I am so happy i fixed my problem, it was all about how i see it. Anyway this dude didnt even helped me at all
I came across some other popular videos explaining this problem, and this is so far the most favorite video which contain the explanation that I am looking for. Thanks alot
Yeah! same feeling here. He makes it clear, simple and visual! I love it!
Great explanation. I have seen many dp solution but nobody explanation as clearly as you did
Happy you feel this
The best explanation I have come across for this problem till date 👍
Thanks!
Thank you so much for the support.
Please make more such amazing videos your explanation is just top notch. Never understood dp tabulation before like this.
I'm glad you liked the explanation!
great approach, thanks teacher, the best explanation I have ever seen
your way of teaching is just great sir , Thanku !!
Thanks and welcome
Amazing explanation of the problem statement and the solution! We had this question in lecture last week and I found it really confusing, thanks for helping out with this Nikhil!!
BEST EXPLANATION TILL DATE ...WOW AMAZING SIR .....Respect +++++++++++++++
Best explanation ever!
Thanks for clearly explaining DP Bottom up approach in normal array traversal instead of reverse traversal. Thanks!
Thanks a lot sir ..u make hard ques in easy way
Great explanation sir .
Please start a playlist of hard DSA problems.
you are such a nice teacher)
man wish I could have you as my tutor..lol..you explain everything so well.
Wow, thanks!
Could you also do a topdown approach please
is the first row (the one with the empty string) also included in the actual dp table or was that only for visualization purposes?
Nice explanation bro👏
You are great Bro, just keep doing
while(true){
print("great explenation")
}
😊
What an explanation 😦😦
Thank you so much brother!
this is everything ...all dp is here
sir sir sir you are a legend
This is no less than excellent !
sir can you explain the backtracking part? To print longest common subsequence
i will make a video on it soon
Sir, in this problem you are iterating from i=1, j=1. but, in the given example the memoization table has dp[0][1]=1. how does it got 1 in program
when you initialize a 2D array, all elements are initialized to 0 by default. That is why I run my loop from i=1, j=1
amazing and detail explained
No recursive brute force for this??????????????
nice explanation
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
// Ensure text1 is the longer string to minimize space usage
if (text2.length() > text1.length()) {
return longestCommonSubsequence(text2, text1);
}
// Convert strings to character arrays for easy access
char[] s1 = text1.toCharArray();
char[] s2 = text2.toCharArray();
// Create two arrays to store the lengths of longest common subsequences
int[] previousRow = new int[s2.length + 1];
int[] currentRow = new int[s2.length + 1];
// Loop through each character in s1
for (int i = 0; i < s1.length; i++) {
// Loop through each character in s2
for (int j = 0; j < s2.length; j++) {
// If characters match, increment the length from the previous row and previous column
if (s1[i] == s2[j]) {
currentRow[j + 1] = previousRow[j] + 1;
} else {
// If characters don't match, take the maximum length by ignoring one character either from s1 or s2
currentRow[j + 1] = Math.max(currentRow[j], previousRow[j + 1]);
}
}
// Swap rows: currentRow becomes previousRow for the next iteration
int[] temp = previousRow;
previousRow = currentRow;
currentRow = temp;
}
// The length of the longest common subsequence is in the last element of previousRow
return previousRow[s2.length];
}
public static void main(String[] args) {
Solution solution = new Solution();
// Test cases
System.out.println(solution.longestCommonSubsequence("abcde", "ace")); // Output: 3
System.out.println(solution.longestCommonSubsequence("abc", "abc")); // Output: 3
System.out.println(solution.longestCommonSubsequence("abc", "def")); // Output: 0
}
} this is true dynamic solution
Sir i love you so much
Thanks Brother
Thanks
Hello Sir, can you make a good video about iteration and loops ? And I hope you will not give the example " You need to repeat 10 times hello, how would you do it ? " ..
What do you want to understand when it comes to loops. I can think on those lines.
@@nikoo28 I dont even know what i'm trying to understand .. I solved 380 problems on LeetCode and still can't really understand them a hundred percent, I use for and while loops to solve problems by pure instinct .. It's like these loops are simulating real world but at a text level , for example if i want to drink a glass of water the translation to text is while ( i still have water in the glass) i keep doing the drinking logic and decrease the water in the glass, but then you have conditions like while (i still have the light on) i keep reading , but that condition is changing based on something decreasing or increasing because mathematics is present in everything right ? we can quantify everything if we really think about it no ? I'm trrying to create this clear picture in my mind comparing programming text and real life and real life to programming text .. Am i overthinking this or I am going crazy ? Please help Sir !
@@exe.m1dn1ght I never imagined a way of comparison like this. I think you should start making videos of how are you relating with real life. A different perspective which will be very cool to know
@@ankurbassi2667 i had a very wrong perspective about this, i figured out its just instructions, like the ones you read on a cooking recipe. I am so happy i fixed my problem, it was all about how i see it. Anyway this dude didnt even helped me at all
best
cudo!
sosote rocafuerte
gracias!!