1143.md

LeetCode #1143: Longest Common Subsequence

🔗 Problem Link: Longest Common Subsequence

Problem Statement 🟡 Difficulty: Medium

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

A subsequence of a string is a new string generated from the original string with some characters deleted (without changing the order of the remaining characters). A common subsequence of two strings is a subsequence that appears in both strings.

The longest common subsequence (LCS) is the longest such sequence among all possible common subsequences.

Example 1:

Input:

text1 = "abcde", text2 = "ace"
Output:
3
Explanation: The LCS is "ace", which has a length of 3.

Example 2:

Input:

text1 = "abc", text2 = "abc"
Output:

3
Explanation: The LCS is "abc", which has a length of 3.

Example 3:

Input:

text1 = "abc", text2 = "def"
Output:

0
Explanation: There is no common subsequence.

Constraints:

1 <= text1.length, text2.length <= 1000
text1 and text2 consist of only lowercase English characters.

Solution Approach: Dynamic Programming (Bottom-Up)

1️ Define the DP State
We use a 2D DP table, dp[i][j], where:

dp[i][j] represents the length of the LCS for text1[i:] and text2[j:].
The extra row and column (filled with zeros) simplify handling edge cases.
2 Recurrence Relation
If text1[i] == text2[j]:
dp[i][j] = 1 + dp[i+1][j+1] (Include this character in the LCS)
Else:
dp[i][j] = max(dp[i+1][j], dp[i][j+1]) (Skip one character from either text1 or text2)
3️ Base Case
If either text1 or text2 is empty, dp[i][j] = 0.