hardDynamic Programming 2DPure DSA~32 min
Config Diff LCS
A config-management tool diffs two ordered lists of directives and wants to know the largest set of lines that appear in both, in the same relative order — the stable core that survived an edit. Compute the length of that longest common subsequence.
Problem
Given two strings a and b, return the length of their longest common subsequence — the longest sequence of characters appearing left-to-right (not necessarily contiguously) in both.
Input
Strings a (length m) and b (length n), 0 ≤ m, n ≤ 1000.
Output
A single integer — the length of the LCS.
Constraints
- 0 ≤ m, n ≤ 1000
- A subsequence need not be contiguous
- Characters are lowercase ASCII letters
Examples
Example 1
Input
a = "abcde", b = "ace"
Output
3
"ace" appears in order in both strings.
Example 2
Input
a = "abc", b = "abc"
Output
3
Identical strings — the whole string is the LCS.