Longest common subsequence

Python data engineering interview problem. Difficulty: intermediate. Pattern: Dynamic Programming. About 16 minutes. Part of the Pro drill bank.

Find the length of the longest subsequence shared between two input text strings. Treat this as a production helper: match the contracted return shape, including empty and duplicate inputs.

Implement longest_common_subsequence(text1: str, text2: str) -> int to compute the length of the longest subsequence present in both strings. A subsequence is a string derived from another string by deleting zero or more characters without changing the relative ordering of the remaining characters. For example, "ace" is a subsequence of "abcde", while "aec" is not. If there is no common subsequence between the two strings, return 0.

Requirements

• Characters in the subsequence must maintain their relative order.
• Return 0 if no common characters exist.

Constraints

• 1 <= len(text1), len(text2) <= 1,000
• text1 and text2 consist only of lowercase English characters.

Examples

Input: longest_common_subsequence('abcde', 'ace') Output: 3 The longest common subsequence is 'ace' with length 3.

Topics: lakebench, python, memoization, grid.

More Python interview questions · All interview problems · Learn data engineering