Simple example
Input
lcs_length("abcde", "ace")
Output
3
The LCS is "ace" which has length 3.
Full lesson preview
Find the longest common subsequence length
Compute the length of the longest common subsequence (LCS) between two strings using dynamic programming.
Python practice15 minDynamic ProgrammingIntermediateLast updated March 29, 2026
Problem statement
Given two strings a and b, return the length of their longest common subsequence (LCS). A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. The goal is to compute the maximum length of a sequence that is a subsequence of both strings. Use a dynamic programming approach (tabulation) to achieve an efficient solution.
Task
Implement a dynamic programming solution to compute the length of the LCS for two input strings.
Examples
Input format
Two strings passed as arguments to function lcs_length(a, b).
Output format
An integer representing the length of the longest common subsequence.
Constraints
0 <= len(a), len(b) <= 2000. Aim for O(len(a) * len(b)) time and O(min(len(a), len(b))) or O(len(a)*len(b)) space.
Samples
Sample 1
Input
lcs_length("ABCBDAB", "BDCABA")
Output
4
One LCS is "BCBA" or "BDAB", both length 4.