v9.1.1
Menu

Longest Common Subsequence

mediumFREEDynamic ProgrammingBlind 75

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
  • text1 and text2 consist of lowercase English letters

Learn this in

More from Blind 75

solution.py

Test results

Sign in to run your code against the test cases.