noodleProblems/
Longest Common Subsequence
#155

Longest Common Subsequence

AlgorithmmediumStringDynamic Programming

Given two strings text1 and text2, return the length of their longest common subsequence.

A subsequence of a string is formed by deleting zero or more characters without disturbing the relative order of the remaining characters — the kept characters don't need to be contiguous. A common subsequence of two strings is a subsequence of both. If the two strings share no characters in common order, return 0.

Example cases

  • interleaved match
    in text1 = "abcde", text2 = "ace"
    out 3
    "ace" is a subsequence of both strings, and no longer common subsequence exists.
  • identical strings
    in text1 = "abc", text2 = "abc"
    out 3
    The whole string is the common subsequence.
  • no shared letters
    in text1 = "abc", text2 = "def"
    out 0

Constraints

  • 1 <= text1.length, text2.length <= 1000
  • text1 and text2 consist of lowercase English letters
Saved
text1 =
"abcde"
text2 =
"ace"