Longest Common Subsequence

The key idea

Build a table dp where dp[i][j] is the LCS length of the first i characters of text1 and the first j characters of text2. When the current characters match, extend the diagonal answer by 1; when they differ, carry the better of the two neighbours (drop a character from one string).

Problem

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.

For example, "ace" is a subsequence of "abcde".

A common subsequence of two strings is a subsequence that is common to both strings.

Constraints

1 <= text1.length, text2.length <= 1000
text1 and text2 consist of only lowercase English characters.

Examples

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

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

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

Complexity

Time: O(m*n) Space: O(m*n)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →