Longest Common Subsequence (DP)

Imagine two friends each write out the story of their week, one event per line. The longest common subsequence is the longest thread of events that show up in both stories, in the same order. The events do not need to sit back-to-back, since other unrelated events can sit in between. It is not about matching whole chunks of text. It is about finding the longest 'both of us did these things, in this order' thread.

1. 1Build a grid where cell (i, j) answers: what is the longest common thread using only the first i letters of string A and the first j letters of string B?
2. 2If the letters at those positions match, the answer is one better than the diagonal cell before it. You extend the thread by one letter.
3. 3If they do not match, the answer is the bigger of two neighboring cells: 'drop this letter from A' or 'drop this letter from B'. Fill the whole grid this way, then walk it backward from the corner to read out the actual matching letters.

Use it to compare two sequences for shared structure — comparing two versions of a file, comparing DNA sequences, spell-check suggestions, or measuring how similar two pieces of text really are, beyond a simple equality check.

• ⚠Confusing 'subsequence' with 'substring'. A subsequence can skip letters and does not need to sit together, so 'ACE' is a subsequence of 'ABCDE' even though the letters are not next to each other.
• ⚠Getting the grid's off-by-one positions wrong. Row and column 0 represent 'zero letters used', so the actual string characters start at position i - 1 and j - 1, not i and j.