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
The best explanation I have come across for this problem till date 👍
Great explanation. I have seen many dp solution but nobody explanation as clearly as you did
Happy you feel this
BEST EXPLANATION TILL DATE ...WOW AMAZING SIR .....Respect +++++++++++++++
great approach, thanks teacher, the best explanation I have ever seen
Thanks for clearly explaining DP Bottom up approach in normal array traversal instead of reverse traversal. Thanks!
your way of teaching is just great sir , Thanku !!
Thanks and welcome
Best explanation ever!
Thanks a lot sir ..u make hard ques in easy way
You are great Bro, just keep doing
this is everything ...all dp is here
Great explanation sir .
Please start a playlist of hard DSA problems.
you are such a nice teacher)
Nice explanation bro👏
Thank you so much brother!
Could you also do a topdown approach please
sir sir sir you are a legend
amazing and detail explained
This is no less than excellent !
nice explanation
Thanks Brother
while(true){
print("great explenation")
}
😊
Thanks!
Thank you so much for the support.
Thanks
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
No recursive brute force for this??????????????
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
best
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
cudo!
sosote rocafuerte
gracias!!