Longest Common Subsequence — Blind 75 practice

Problem

Given two strings text1 and text2, return the length of their longest common subsequence — the longest sequence of characters appearing in both, in the same order, not necessarily adjacent.
"ace" is a subsequence of "abcde"; "aec" is not. No common subsequence means 0.

Examples

Example 1:
Input: text1 = "abcde", text2 = "ace"
Output: 3

Example 2:
Input: text1 = "abc", text2 = "abc"
Output: 3

Example 3:
Input: text1 = "abc", text2 = "def"
Output: 0

Example 4:
Input: text1 = "ezupkr", text2 = "ubmrapg"
Output: 2

Constraints

1 <= text1.length, text2.length <= 1000
Both strings consist of lowercase English letters.

Prerequisites

Dynamic programming — being able to say, in one sentence, what a single cell of your table MEANS. Everything else follows from that sentence.
Rolling variables: when a state only looks back one or two steps, the table collapses to a couple of numbers.

How to think about it

1. Table Over Prefix Pairs Optimal

Intuition

lcs[i][j] means "the longest common subsequence of the first i characters of one string and the first j of the other". With that sentence the two cases are obvious: if those last characters match, they can both be taken, extending the diagonal; if not, drop one character from one side or the other and keep the better. Two rolling rows are enough since a cell only reads the row above and the cell to its left.

Algorithm

1. An empty prefix shares nothing: all zeros.
2. Matching last characters: one plus the diagonal.
3. Otherwise: the better of dropping from either string.
4. The bottom-right cell is the answer.

Time & Space

Time O(m*n). Space O(min(m, n)) with rolling rows.