Longest common subsequence

Find a longest sequence appearing in both inputs in the same order, allowing gaps.

Remember: Same: diagonal + 1. Different: best of above or left.

Example: ABC and AC → AC, length 2.

Time: O(mn). Auxiliary space: O(mn).

Formula: Equal: 1 + diagonal. Different: max(above, left).

Up to 6 Unicode code points per sequence; matching is case-sensitive. A subsequence preserves order but need not be contiguous. Both methods recover one optimal answer. Memoization adds an O(m + n) call stack; both allocate the full table. ? cells were not needed or have not been computed.

Complexities describe the underlying algorithm; tutorial snapshots and rendering can use additional resources.

The interactive workspace loads here when JavaScript is available. You can still browse the learning notes and links above without it.