@algorithm.ts/lcs

@algorithm.ts/lcs is a zero-dependency TypeScript package (part of the algorithm.ts monorepo) dedicated to solving the longest common subsequence (LCS) problem — the same core comparison logic behind tools like diff and Git’s merge machinery. Rather than committing to one implementation, it exposes three: a straightforward dynamic-programming solver that also returns the minimal lexicographical match, the classic Myers O(ND) diff algorithm, and a linear-space refinement of Myers for when memory matters more than raw speed.

Every function operates on index pairs and a caller-supplied equals(x, y) comparator instead of requiring arrays of a specific element type, so it works identically over strings, numbers, objects, or any other indexable sequence. That makes it a drop-in primitive for anything that needs to compute or visualize differences between two ordered collections without pulling in a full diffing framework.

What You Get

• lcs_dp / lcs_myers / lcs_myers_linear_space — three algorithms returning the same [i, j] index-pair result shape, so they can be swapped based on time/space tradeoffs
• lcs_size_dp / lcs_size_myers / lcs_size_myers_linear_space — length-only counterparts that skip building the full match array when only the LCS length is needed
• findLCSOfEveryRightPrefix — a rolling-array DP variant that returns the LCS length for every prefix pair in a single pass, useful for incremental/streaming comparisons
• Comparator-based API (equals(x, y) over indices) that works on any indexable sequence type — strings, number arrays, or arbitrary objects — not just a hardcoded element type
• Dual ESM/CJS builds with bundled .d.ts type declarations and zero runtime dependencies

Common Use Cases

• Implementing a text-diff or patch utility that needs to align two versions of a document line-by-line or token-by-token
• Building a merge/reconciliation step for version-controlled or collaboratively-edited data structures
• Fuzzy-matching or sequence-alignment tasks in data pipelines where the minimal lexicographical LCS is required for deterministic output
• Computing similarity scores between two ordered collections (e.g. tag lists, event sequences) via LCS length alone, without needing the full alignment

Under The Hood

Architecture The package splits its three algorithms into isolated submodules (src/dp, src/myers, src/myers_linear_space), each exporting a paired lcs and lcs_size function, and re-exports everything through a single src/index.ts barrel alongside two readability aliases (findMinLexicographicalLCS, findLengthOfLCS). There is no shared class hierarchy or internal state — every function is a pure, self-contained closure over its own diagonals/parents bookkeeping (in the Myers variants) or its own DP table (in the DP variant), so the three implementations can be swapped or dropped independently without touching the others.

Tech Stack Written in TypeScript 5.9 with no runtime dependencies, built through the monorepo’s shared Rollup pipeline (@rollup/plugin-typescript plus rollup-plugin-dts) into dual ESM/CJS bundles with generated .d.ts declarations, and versioned/published via pnpm workspaces with Changesets. Tests run on Vitest, configured once at the repo root and reused by every package.

Code Quality A dedicated __test__/lcs.spec.ts suite exercises all three implementations against shared fixture cases — including empty sequences, single-character edge cases, and long randomized UUID strings — verifying both LCS length and exact minimal lexicographical alignment where applicable. Coverage thresholds are configured per package, a GitHub Actions CI workflow runs on every push, and ESLint plus Prettier are enforced repo-wide. Types are explicit throughout (no implicit any), and naming is consistent across the three algorithm variants.

API Design The comparator-based (N1, N2, equals) signature is unusual compared to a typical lcs(a, b) API, but it is a deliberate tradeoff: it lets the same function operate over strings, number arrays, or arbitrary objects without generic constraints, and lets size-only callers avoid passing full sequences at all. The tradeoff is a small amount of extra boilerplate at the call site (index-based comparators instead of direct element access) in exchange for broader reuse and a zero-copy calling convention.