#0244

Longest Common Subsequence

MediumDSA28 min20 XP

Problem

Given strings a and b, return the length of their longest common subsequence. Characters must keep order, but they do not need to be contiguous.

Why This Matters

LCS is the core 2D DP pattern behind diff tools, edit distance, and sequence alignment.

Function Signature

def lcs_length(a, b):

Examples

Example 1

Inputa = "abcde", b = "ace"

Output3

ace appears in both strings in order.

Constraints

Return the exact requested value.
Handle empty or small inputs when the prompt allows them.
Prefer the target DSA pattern over brute force when the input can grow.

CodePython

def lcs_length(a, b):
    """
    Input example: a = "abcde", b = "ace"
    Return: 3
    Return the value from the function so the tests can compare it. Do not print unless the prompt asks.
    """
    # write your code here
    return 0

def lcs_length(a, b):
    """
    Input example: a = "abcde", b = "ace"
    Return: 3
    Return the value from the function so the tests can compare it. Do not print unless the prompt asks.
    """
    # write your code here
    return 0

Visible browser tests run here when available.

Testcases2 visible / 3 hidden categories

Subsequence not substring

Inputabcde, ace

Expected3

The matching characters do not need to be adjacent.

No common characters

Inputabc, def

Expected0

No character can be matched.

Hidden Test Categories

one empty stringidentical stringsrepeated characters