Longest Common Subsequence — Medium Coding Interview Question

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

Example

Input: text1 = "abcde", text2 = "ace"

Output: 3

Explanation: LCS is 'ace'.

Constraints

• 1 ≤ text1.length, text2.length ≤ 1000

Topics & Companies

Topics: dp

Asked by: Amazon, Google, Meta, Microsoft, Apple, Bloomberg

Optimal Solution Complexity

Time complexity: O(m×n). Space complexity: O(n).

Practice more

• All DSA Problems
• DSA Patterns