The Longest Common Subsequence (LCS) problem is one of the most important String Dynamic Programming interview questions.

A subsequence is formed by deleting zero or more characters without changing the relative order of the remaining characters.

Goal:

Find the length of the longest subsequence common to both strings.

Example

text1 = "abcde"
text2 = "ace"
Output = 3 

Explanation:

Common Subsequence = "ace"Length = 3

Constraints

1 <= text1.length <= 10001 <= text2.length <= 1000

Key Observation

If characters match:

dp[i][j] = 1 + dp[i-1][j-1] 

If characters do not match:

dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 

This forms the DP recurrence.

Approach 1 : Memoization

Explanation

Use recursion and store previously computed results.

Steps:

1. Compare characters.
2. If equal, include the character.
3. If different, try both possibilities.
4. Store results.
5. Reuse answers.

Approach 2 : Tabulation

Explanation

Build a DP table from smaller prefixes.

Base Case:

Empty string has LCS length 0. 

Transition:

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

Dry Run

Input:

text1 = "abcde"text2 = "ace"

DP Table:

    a c e
  0 0 0 0
a 0 1 1 1
b 0 1 1 1
c 0 1 2 2
d 0 1 2 2
e 0 1 2 3 

Answer:

3 

Approach 3 : Space Optimized DP

Explanation

Instead of storing the entire matrix:

m × n 

Store only the previous row.

This reduces memory usage.

Practice

Memoization
Time Complexity: O(m × n)
Space Complexity: O(m × n)

Tabulation
Time Complexity: O(m × n)
Space Complexity: O(m × n)

Space Optimized DP
Time Complexity: O(m × n)
Space Complexity: O(n) 

If characters match:Take diagonal + 1

Else:
Take maximum of top and left.