Course4all
Join us on telegram
Home/dsa/Dynamic Programming/Longest Common Subsequence

Longest Common Subsequence

Master this topic with zero to advance depth.

Longest Common Subsequence

Given two strings text1 and text2, return the length of their longest common subsequence. 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.

Visual Representation

text1 = "abcde", text2 = "ace" LCS is "ace", Length = 3 DP Grid Logic: - If text1[i] == text2[j]: 1 + dp[i+1][j+1] (Match!) - Else: max(dp[i+1][j], dp[i][j+1]) (Skip one char)
Medium

Examples

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

The longest common subsequence is "ace" and its length is 3.

Input: text1 = "abc", text2 = "abc"
Output: 3
Approach 1

Level I: Brute Force (Recursive)

Intuition

We compare characters of both strings starting from the beginning. If they match, we increment the count and move both pointers. If they don't match, we have two choices: skip a character from text1 or skip a character from text2. We take the maximum of these two paths.

Thought Process

  1. solve(i, j): LCS of text1[i:] and text2[j:].
  2. If text1[i] == text2[j]: 1 + solve(i+1, j+1).
  3. Else: max(solve(i+1, j), solve(i, j+1)).

Pattern Identification

This is Recursive Decision Tree. The time complexity is exponential because it explores the same (i, j) pairs multiple times.

⏱ O(2^(n+m))💾 O(n+m) for recursion stack

Detailed Dry Run

text1="abc", text2="ace"

ijMatch?ActionReturns
00'a'=='a' (Yes)1 + f(1, 1)1 + 2 = 3
11'b'=='c' (No)max(f(2, 1), f(1, 2))max(1, 2) = 2
12'b'=='e' (No)max(f(2, 2), f(1, 3))max(1, 0) = 1
java
public class Main {
    public static int lcs(String s1, String s2, int i, int j) {
        if (i == s1.length() || j == s2.length()) return 0;
        if (s1.charAt(i) == s2.charAt(j)) {
            return 1 + lcs(s1, s2, i + 1, j + 1);
        } else {
            return Math.max(lcs(s1, s2, i + 1, j), lcs(s1, s2, i, j + 1));
        }
    }

    public static void main(String[] args) {
        System.out.println(lcs("abcde", "ace", 0, 0)); // 3
    }
}
Approach 2

Level II: Memoization (Top-Down 2D)

Intuition

The recursive LCS solution re-evaluates the same (i, j) pairs many times. We add a 2D memo table indexed by string positions.

Visual

text1="abc", text2="ace" Memo table after caching: "" 'a' 'c' 'e' "" 0 0 0 0 'a' 0 [3] - - <- solve(0,0)=3 cached! 'b' 0 - - - 'c' 0 - [1] -
⏱ O(N * M)💾 O(N * M)

Detailed Dry Run

solve(0, 0): 'a'=='a', return 1+solve(1,1). solve(1,1): 'b'!='c', return max(solve(2,1), solve(1,2)).

java
import java.util.*;

public class Main {
    static int[][] memo;
    public static int solve(String s1, String s2, int i, int j) {
        if (i == s1.length() || j == s2.length()) return 0;
        if (memo[i][j] != -1) return memo[i][j];
        if (s1.charAt(i) == s2.charAt(j)) return memo[i][j] = 1 + solve(s1, s2, i+1, j+1);
        return memo[i][j] = Math.max(solve(s1, s2, i+1, j), solve(s1, s2, i, j+1));
    }

    public static int longestCommonSubsequence(String text1, String text2) {
        memo = new int[text1.length()][text2.length()];
        for (int[] row : memo) Arrays.fill(row, -1);
        return solve(text1, text2, 0, 0);
    }

    public static void main(String[] args) {
        System.out.println(longestCommonSubsequence("abcde", "ace")); // 3
    }
}

⚠️ Common Pitfalls & Tips

Python's lru_cache automatically creates the 2D memo table. In Java, a 2D array initialized with -1 suffices for string indices.

Approach 3

Level III: Optimal (2D DP)

Intuition

Thought Process

We use a 2D grid where dp[i][j] represents the LCS length for text1[i:] and text2[j:]. We fill the grid from the bottom-right towards the top-left (or top-left to bottom-right).

Logic Steps

  1. Initialize a 2D array dp of size (m+1) x (n+1) with 0s.
  2. Iterate through i (text1) and j (text2) in reverse.
  3. If characters match: dp[i][j] = 1 + dp[i+1][j+1].
  4. Else: dp[i][j] = max(dp[i+1][j], dp[i][j+1]).
  5. Return dp[0][0].
⏱ O(N * M) where N, M are lengths of the strings💾 O(N * M)

Detailed Dry Run

text1="abc", text2="ace"

Row (i)Col (j)Match?dp[i][j] calculationValue
2 (c)2 (e)Nomax(dp[3][2], dp[2][3])0
2 (c)1 (c)Yes1 + dp[3][2]1
1 (b)1 (c)Nomax(dp[2][1], dp[1][2])1
0 (a)0 (a)Yes1 + dp[1][1]3
java
public class Main {
    public static int longestCommonSubsequence(String text1, String text2) {
        int[][] dp = new int[text1.length() + 1][text2.length() + 1];

        for (int i = text1.length() - 1; i >= 0; i--) {
            for (int j = text2.length() - 1; j >= 0; j--) {
                if (text1.charAt(i) == text2.charAt(j)) {
                    dp[i][j] = 1 + dp[i + 1][j + 1];
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j + 1]);
                }
            }
        }
        return dp[0][0];
    }

    public static void main(String[] args) {
        System.out.println(longestCommonSubsequence("abcde", "ace")); // 3
    }
}

⚠️ Common Pitfalls & Tips

Remember to initialize the dp table with size (n+1) x (m+1) to handle the base cases (empty strings) easily without extra boundary checks.

← Previous QuestionJump Game
Next Question →Word Break