AceYourInterviews
Checking sign-in…

134. Longest Common Subsequence

AdvancedTwo-prefix alignment DP with a saved diagonal

Find the longest sequence of character units that can be obtained from each string by deleting some positions without reordering the remaining positions. Return its length.

The matching positions may have gaps in both strings. This is a subsequence problem, not a search for a common contiguous substring.

Example 1

Input

a="abcde", b="ace"

Output

3

Explanation: a,c,e appear in order in both, although they are not contiguous in abcde.

Example 2

Input

a="abc", b="xyz"

Output

0

Explanation: No matching code unit can contribute.

Example 3

Input

a="ab", b="ba"

Output

1

Explanation: Either a or b is common, but both cannot appear in the required order.

Example 4

Input

a="😀", b="😀"

Output

2

Explanation: The identical surrogate pair contributes two UTF-16 code units under this explicit contract.

Constraints

  • 0 <= a.length, b.length <= 2000
  • Compare UTF-16 code units exactly, with case sensitivity.
Hints
Hint 1

Define an optimum for two prefixes, including empty prefixes.

Hint 2

If the final code units differ, what must a common sequence omit? What happens when they match?

Hint 3

In one row, dp[j] is old up and dp[j−1] is new left; save diagonal separately.

Practice on LeetCode ↗
Code
Saved on this deviceLn 1, Col 1

Gaps preserve previous matches

"abc"
"ac"
2