When two versions of a text differ, what actually changed? The trick is to find the LONGEST run of characters they still share in order — the longest common subsequence — and everything outside it is an addition or a deletion. Every ‘diff’ you have ever seen is this. Slide between text pairs and watch the common thread light up.
The longest common subsequence is filled by a grid: d[i][j] = d[i−1][j−1]+1 on a match, else the better of dropping a character from either side. Tracing back yields the characters both strings keep, IN ORDER; the rest are deletions (in the old only) or insertions (in the new only). A fail-loud self-check throws unless the recovered LCS is a genuine subsequence of BOTH strings and has the known optimal length — the exact skeleton every version-control diff is built on.
Character-level LCS here; real diffs work on lines and add heuristics (Myers’ algorithm, patience diff) for readable hunks. The LCS length and its subsequence-of-both property are exact.