What is Longest common subsequence?

The longest common subsequence problem finds the longest sequence of elements appearing in the same order in two inputs, though not necessarily contiguously. It is the basis of most text diff algorithms.