Skip to main content
Back to ChallengesLongest Common Subsequence (LCS)Medium 30 min

Longest Common Subsequence (LCS)

Given two strings text1 and text2, return the length of their longest common subsequence. A subsequence is a string generated by deleting some or no characters without changing relative order.

Examples

Input: text1 = 'abcde', text2 = 'ace'
Output: 3
The LCS is 'ace', length 3.
Input: text1 = 'abc', text2 = 'def'
Output: 0
No common characters.

Constraints

  • • 1 <= text1.length, text2.length <= 1000
  • • Strings contain only lowercase English characters.

Complexity Analysis

Time
O(m * n)
where m and n are string lengths.
Space
O(m * n)
storing 2D array state.

Test Cases

#1 LCS exists
Input: "abcde", "ace"
Expected: 3
#2 Identical strings
Input: "abc", "abc"
Expected: 3
#3 Completely disjoint strings
Input: "abc", "def"
Expected: 0
JavaScript
Output
Click "Run Code" to see output here...