v9.1.1
Menu

Longest Common Subsequence

mediumPRODynamic ProgrammingDSA for AI Engineers

Given two strings, return the length of their longest common subsequence (LCS). A subsequence maintains relative order but needn't be contiguous.

Example

Input
abcde
ace
Output
3
Reasoning
  • The inputs are two lowercase strings, text1 = abcde (length 55) and text2 = ace (length 33). A common subsequence is a string you can get from both by deleting characters without reordering the ones that remain.
  • Delete b and d from abcde and you get ace, which is already all of text2. So ace is a common subsequence of length 33.
  • No common subsequence can be longer than the shorter string, and text2 only has 33 characters. So 33 is the maximum and the output is 3.
  • Order matters, not just shared letters. If the second string were "aec", both strings would still contain a, c and e, but in abcde the c comes before the e. The best you could keep is "ac" or "ae", so the answer would drop to 22.
  • Notice that the output is a single integer, the length. You never need to return the subsequence itself, and when two strings share no letters at all the answer is 00.

Constraints

  • 1 <= len(text1), len(text2) <= 1000
  • Strings consist of lowercase English letters

More from DSA for AI Engineers

PRO

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Test results

Sign in to run your code against the test cases.