Length of the Longest Common Subsequence

Given two strings, find the length of their longest common subsequence. A subsequence is a sequence that appears in the same relative order but not necessarily consecutively.

Input-Output Examples

Example 1:
Input: s1 = "abcde", s2 = "ace"
Output: 3

Example 2:
Input: s1 = "abc", s2 = "abc"
Output: 3

Example 3:
Input: s1 = "abc", s2 = "def"
Output: 0

Approach:
Technique: Dynamic Programming

  1. Initialization: Create a 2D array dp where dp[i][j] represents the length of the LCS of s1[0..i-1] and s2[0..j-1].
  2. Filling the DP Table:
    • If s1[i-1] == s2[j-1], then dp[i][j] = dp[i-1][j-1] + 1.
    • Otherwise, dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
  3. Return: The value dp[m][n] (where m and n are the lengths of s1 and s2, respectively) contains the length of the LCS.

C++ Program to find the length of the Longest Common Subsequence

cpp
#include <iostream>
#include <vector>
#include <string>
using namespace std;

// Function to find the length of the longest common subsequence
int longestCommonSubsequence(string s1, string s2) {
    int m = s1.size(), n = s2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
}

int main() {
    string s1 = "abcde";
    string s2 = "ace";
    int length = longestCommonSubsequence(s1, s2);
    cout << "Length of Longest Common Subsequence: " << length << endl;
    return 0;
}

Java Program to find the length of the Longest Common Subsequence

java
public class LongestCommonSubsequence {
    public static void main(String[] args) {
        String s1 = "abcde";
        String s2 = "ace";
        int length = longestCommonSubsequence(s1, s2);
        System.out.println("Length of Longest Common Subsequence: " + length);
    }

    // Function to find the length of the longest common subsequence
    public static int longestCommonSubsequence(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }
}

Python Program to find the length of the Longest Common Subsequence

python
def longestCommonSubsequence(s1: str, s2: str) -> int:
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

if __name__ == "__main__":
    s1 = "abcde"
    s2 = "ace"
    length = longestCommonSubsequence(s1, s2)
    print(f"Length of Longest Common Subsequence: {length}")

DSA

4960

754

Related Articles