Longest Common Subsequence (LCS)

The LCS problem finds the longest sequence that appears in the same relative order in two strings. It is the core algorithm behind Git Diff, File Comparisons, and DNA Sequencing.

1. Substring vs Subsequence

• Substring: Must be contiguous (e.g., "ABCD" in "ABCDEFG").
• Subsequence: Does NOT have to be contiguous (e.g., "ACE" in "ABCDE").

2. The LCS Table

If characters match: dp[i][j] = 1 + dp[i-1][j-1]. If they don't: dp[i][j] = Max(dp[i-1][j], dp[i][j-1]). This builds a matrix from the bottom up, with the final answer sitting at the bottom-right cell.

4. Interview Mastery

Q: "How does Git use the LCS algorithm?"

Architect Answer: "Git calculates the LCS of two file versions. Any lines (characters) NOT in the LCS are considered 'Changes' (Additions or Deletions). By finding the longest common part, Git can minimize the 'Noise' in a diff and show the developer exactly what changed as efficiently as possible."