Facebook PixelLongest Common Subsequence — Coding Practice
Longest Common SubsequenceMedium

Longest Common Subsequence

Medium 11.2k58% acceptance
StringDynamic Programming

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence keeps the original left-to-right order but may skip characters. A common subsequence is one that appears in both strings.

Example 1
Input: text1 = "abcde", text2 = "ace"
Output: 3
"ace" appears in order in both strings and is the longest such subsequence.
Example 2
Input: text1 = "abc", text2 = "abc"
Output: 3
The whole string is common.
Example 3
Input: text1 = "abc", text2 = "def"
Output: 0
No character is shared, so there is no common subsequence.
Constraints
  • 1 ≤ text1.length, text2.length ≤ 1000
  • Both strings consist of lowercase English letters.
Asked atAmazonGoogleMicrosoftAdobe
JavaScript
Loading editor…
Case 1
"abcde", "ace"
expected: 3
Case 2
"abc", "abc"
expected: 3
Case 3
"abc", "def"
expected: 0
Case 4
"bsbininm", "jmjkbkjkv"
expected: 1
Case 5
"oxcpqrsvwf", "shmtulqrypy"
expected: 2
Case 6
"a", "a"
expected: 1
Case 7
"ezupkr", "ubmrapg"
expected: 2