Longest Common Subsequence (LeetCode 1143) | Full Solution with a natural explanation

[@anushakatika9229]

Great explanation. I have seen many dp solution but nobody explanation as clearly as you did

[@nikoo28]

Happy you feel this

[@ashok2089]

Thanks for clearly explaining DP Bottom up approach in normal array traversal instead of reverse traversal. Thanks!

[@Usseeer_kaizen]

great approach, thanks teacher, the best explanation I have ever seen

[@Hayat26474]

your way of teaching is just great sir , Thanku !!

[@nikoo28]

Thanks and welcome

[@ishaqniloy1532]

Best explanation ever!

[@urvashichaurasia6284]

Great explanation sir .
Please start a playlist of hard DSA problems.

[@sheikhmkrifat7749]

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

[@acthanger7420]

you are such a nice teacher)

[@vivekkumaryadav9862]

Thanks a lot sir ..u make hard ques in easy way

[@hoddybhaba6704]

Nice explanation bro👏

[@rode_atharva]

while(true){
print("great explenation")
}

[@nikoo28]

😊

[@lo_sten]

Could you also do a topdown approach please

[@jayaveeran1]

This is no less than excellent !

[@himanshuajwani9226]

amazing and detail explained

[@EgorChebotarev]

nice explanation

[@vishwasankar14]

Thank you so much brother!

[@subee128]

Thanks

[@anushakatika9229]

Thanks!

[@nikoo28]

Thank you so much for the support.

[@alisheheryar1770]

No recursive brute force for this??????????????

[@AmalGeorge-xt3kq]

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

[@nikoo28]

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

[@shadowwolf5578]

sir can you explain the backtracking part? To print longest common subsequence

[@nikoo28]

i will make a video on it soon

[@ifrahshahid8802]

best

[@exe.m1dn1ght]

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]

What do you want to understand when it comes to loops. I can think on those lines.

[@exe.m1dn1ght]

@@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 !

[@RamuKumar-yl4yp]

​

[@ankurbassi2667]

@@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

[@exe.m1dn1ght]

@@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

[@dmytro.pyvovarenko]

cudo!

[@luiggymacias5735]

sosote rocafuerte

[@nikoo28]

gracias!!