Longest Common Subsequence Finder
Find one longest subsequence shared by two strings using dynamic programming.
Description
Find the length and one longest ordered subsequence shared by two strings.
A common subsequence preserves order without requiring adjacent characters. Longest common subsequences underpin sequence comparison, diff concepts, and classic dynamic-programming exercises.
When to use Longest Common Subsequence Finder
- Find a shared ordered character sequence
- Study dynamic programming
- Compare versions dominated by insertions and deletions
How the calculation works
A prefix table stores best lengths, then backtracking reconstructs one maximum answer. The implementation compares Unicode code points rather than splitting non-BMP characters into UTF-16 halves.
Interpreting the result
Several equally long answers can exist; the tie rule returns one deterministic sequence. The reported length counts code points, and matching characters need not be contiguous.
Important limitations
- Time and memory grow with the product of input lengths.
- A four-million-cell budget is enforced.
- Comparison is exact and does not normalize case or Unicode.