Longest Common Subsequence

Difficulty: Hard · Topic: Dynamic programming

Given strings a and b, return the length of their longest common subsequence (characters in order, not necessarily contiguous). Fill a 2D table: when characters match, extend the diagonal; otherwise take the best of dropping a character from either string.

Examples

longest_common_subsequence("abcde", "ace")
→ 3

'ace'.

longest_common_subsequence("abc", "abc")
→ 3

longest_common_subsequence("abc", "def")
→ 0

Target complexity: time O(m · n), space O(m · n)

Write your solution in Python and run it against hidden tests right on this page. Progressive hints and Python + C++ reference solutions are included.

Learn the idea first: the lesson for this problem.