LCS Dynamic Programming in Java: Fill the Table, Then Print the Subsequence | DSA Course L77

Lecture 77 of the Complete DSA Course in Java by Engineer X · Part 4: Dynamic Programming, Greedy and Amortized Analysis. In this lecture • Why row-major order works: every cell needs only up, left and the diagonal • Bottom-up LCS length in Java, with Java's zeros as free base cases • The whole c table filled for SINGLE and STRING, cell by cell with arrows • Θ(mn) time and space, instead of exponential recursion • Recovering the letters: the book's arrow table b, and why an up-left arrow is a match • Dropping b: reading each cell's origin straight from c, walked back in O(m + n) • Two rows of memory for the length only, and why they cannot rebuild the letters • Interview: how diff tools use LCS, and which string should index the columns Chapters 0:00 From recurrence to table 1:08 The Java code 2:06 Watch the table fill 3:51 Time and space 4:13 Walking back to the answer 7:07 Improving the code 8:04 Interview: how diff works 8:38 Recap and quiz 9:40 Up next Book reference: Introduction to Algorithms (Cormen, Leiserson, Rivest, Stein), 4th edition, Section 14.4. The explanations, examples and code in this lecture are original. #DSA #Algorithms #DataStructures #Java #CodingInterview #EngineerX #LongestCommonSubsequence #LCS #DynamicProgramming #Java #CLRS