Neural Mastery
← Practice
Longest Common Subsequencemedium

Longest Common Subsequence

medium Coding Interview Patterns 15–20 min

NumPy allowed · plain Python earns 10 bonus points

Find the length of the longest subsequence shared between two text sequences using 2D DP.

Task

Implement longest_common_subsequence(text1, text2): if text1[i] == text2[j], dp[j] = prev + 1; otherwise dp[j] = max(dp[j], dp[j-1]).

Function Signature

longest_common_subsequence(text1: str, text2: str) -> int

Examples

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

Constraints

  • 1 <= len(text1), len(text2) <= 1000
  • text1 and text2 consist of only lowercase English characters.
Python3Saved ✓
def longest_common_subsequence(text1: str, text2: str) -> int:
"""text1, text2: two input strings.
Return the length of their longest common subsequence.
A subsequence is derived by deleting zero or more characters without changing relative order."""
# Your implementation here
pass

Case 1: text1="abcde", text2="ace"
Input: text1 = 'abcde' text2 = 'ace'
Expected: 3
Case 2: text1="abc", text2="abc"
Input: text1 = 'abc' text2 = 'abc'
Expected: 3