मुख्य कंटेंट तक स्किप करें
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...