Longest Common Subsequence

Problem

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

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

For example, "ace" is a subsequence of "abcde", but "aec" is not.

A common subsequence of two strings is a subsequence that is common to both strings.

Input / Output Format

Input:

• text1 — a string consisting of lowercase English letters
• text2 — a string consisting of lowercase English letters

Output:

• An integer representing the length of the longest common subsequence of text1 and text2

Examples

Example 1

Input: text1 = "abcde", text2 = "ace" Output: 3 Explanation: The longest common subsequence is "ace", which has length 3.

Example 2

Input: text1 = "abc", text2 = "abc" Output: 3 Explanation: The longest common subsequence is "abc" itself.

Example 3

Input: text1 = "abc", text2 = "def" Output: 0 Explanation: There is no character in common between the two strings, so the LCS is empty.

Approach Hints

This is a classic Dynamic Programming problem.

1. Define subproblems: Let dp[i][j] represent the length of the LCS of text1[0..i-1] and text2[0..j-1].

2. Recurrence relation:

   • If text1[i-1] == text2[j-1]: dp[i][j] = dp[i-1][j-1] + 1
   • Otherwise: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

3. Base case: dp[0][j] = 0 and dp[i][0] = 0 for all i, j.

4. Result: dp[m][n] where m = len(text1) and n = len(text2).

Time Complexity: O(m × n) where m and n are the lengths of text1 and text2.

Space Complexity: O(m × n), or O(min(m, n)) with space optimization.