Longest Common Subsequence
Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.
A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.
Examples
Input: ["abcde","ace"]
Output: 3
Input: ["abc","abc"]
Output: 3
Hints
Visualize the problem as a grid where rows represent characters of `text1` and columns represent characters of `text2`. The cell at `(i, j)` stores the LCS length for `text1[0..i-1]` and `text2[0..j-1]`.
Observe that if the current characters match (`text1[i-1] == text2[j-1]`), the LCS length increases by 1 from the diagonal cell (`dp[i-1][j-1]`). Otherwise, take the maximum of the cell above (`dp[i-1][j]`) or the cell to the left (`dp[i][j-1]`).
Optimize space complexity by reducing the 2D DP table to two 1D arrays (or even a single array) since only the previous row/column is needed to compute the current cell.
Related Problems
Longest Common Subsequence
Given two strings `text1` and `text2`, return the length of their **longest common subsequence**. If there is no common subsequence, return `0`.