Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Table of contents

1.

Introduction

2.

Problem Statement

2.1.

Example:

3.

Longest Common Subsequence Algorithm

4.

Longest Common Subsequence (LCS) using Recursion

4.1.

Implementation

4.2.

C

4.3.

C++

4.4.

Java

4.5.

Python

4.6.

Javascript

4.7.

PHP

4.8.

C#

4.9.

Time and Space Complexity

5.

Longest Common Subsequence (LCS) Using Dynamic Programming

5.1.

1. Longest Common Subsequence (LCS) Using Top-Down Dp

5.1.1.

Implementation

5.2.

C

5.3.

C++

5.4.

Java

5.5.

Python

5.6.

Javascript

5.7.

PHP

5.8.

C#

5.8.1.

Time and Space Complexity

5.9.

2. Longest Common Subsequence (LCS) Using Bottom-Up Dp

5.9.1.

Implementation

5.10.

C

5.11.

C++

5.12.

Java

5.13.

Python

5.14.

Javascript

5.15.

PHP

5.16.

C#

5.16.1.

Time and Space Complexity

6.

Longest Common Subsequence Applications

7.

Frequently Asked Questions

7.1.

What is meant by longest common subsequence?

7.2.

Why do we use LCS?

7.3.

What are the conditions for LCS algorithm?

7.4.

What is the recursive formula for LCS?

7.5.

What is the longest common subsequence measure?

7.6.

What is the longest common subsequence of an array?

7.7.

What is the longest common subsequence in linear space?

8.

Conclusion

Last Updated: Sep 19, 2024

Medium

Longest Common Subsequence (LCS)

Author Raksha Jain

Introduction

In algorithmic problem-solving, the Longest Common Subsequence (LCS) stands as a fundamental concept with applications spanning from computational biology to data compression. LCS seeks to find the longest sequence that can be derived from two or more sequences, maintaining the order of elements without necessarily being contiguous. Understanding LCS involves delving into dynamic programming strategies, sequence alignment techniques, and real-world scenarios where it plays a pivotal role in pattern recognition and similarity analysis.

longest common subsequence

What is Recursion

Problem Statement

Given two strings, s1 and s2, find 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 (or none) characters deleted without changing the relative order of the remaining characters.

So, if a string is “abcde,” some of the possible subsequences of the given string are “cde,” “bc,” etc.

However, “bae” is not a valid subsequence as the relative ordering of characters is not maintained.

Example:

Let the two strings be “acbaed” and “abcadf.”

The longest Common Subsequence of the strings is “acad,” as this subsequence is present in both string1 and string2 and is the longest one.

So, the length of Longest Common Subsequence = size of “acad” = 4.

Problem Statement

Let's consider another example: Let the two strings be “acb” and “dfe”.

The longest Common Subsequence of the strings is “” (empty string) as it has no subsequence, which is present in both string1 and string2.

So, the length of Longest Common Subsequence = length of “” = 0.

Now, let's get started and learn various approaches to solve this problem.

Longest Common Subsequence Algorithm

There exist multiple algorithms to determine the longest common subsequence between two strings, each varying in time and space complexities while addressing the same problem. Subsequent sections will explore these distinct approaches for finding the longest common subsequence.

Longest Common Subsequence (LCS) using Recursion

The naive (or brute force) solution to this problem could be finding all possible configurations of different subsequences and finding the longest common subsequence possible.

So, we maintain two indexes, i and j, one for each string and increment one by one to find the best possible solution.

Note: If any of the indices reach any of the string’s length, the longest common subsequence would be 0 as the range to find the longest common subsequence.

Implementation

Let’s have a look at its implementation:

C

#include <stdio.h>
#include <string.h>

int LCS(char s1[], char s2[], int i, int j) {
    // Base case
    if (s1[i] == '\0' || s2[j] == '\0') return 0;

    if (s1[i] == s2[j]) {
        return 1 + LCS(s1, s2, i + 1, j + 1);
    }

    int option1 = LCS(s1, s2, i + 1, j);
    int option2 = LCS(s1, s2, i, j + 1);

    return (option1 > option2) ? option1 : option2;
}

int main() {
    char s1[100], s2[100];

    // Take Input
    printf("Enter String1: ");
    scanf("%s", s1);

    printf("Enter String2: ");
    scanf("%s", s2);

    int lcsans = LCS(s1, s2, 0, 0);

    printf("Longest Common Subsequence: %d\n", lcsans);

    return 0;
}

You can also try this code with Online C Compiler

C++

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

int LCS(string s1, string s2, int i, int j) {
    // Base case
    if (i == s1.length() || j == s2.length()) return 0;

    if (s1[i] == s2[j]) {
        return 1 + LCS(s1, s2, i + 1, j + 1);
    }

    int option1 = LCS(s1, s2, i + 1, j);
    int option2 = LCS(s1, s2, i, j + 1);

    return max(option1, option2);
}

int main() {
    string s1, s2;

    // Take Input
    cout << "Enter String1: ";
    cin >> s1;

    cout << "Enter String2: ";
    cin >> s2;

    int lcsans = LCS(s1, s2, 0, 0);

    cout << "Longest Common Subsequence: " << lcsans << endl;

    return 0;
}

You can also try this code with Online C++ Compiler

Java

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Solution {

  // Using recursive approach
    public static int LCS(String s1, String s2, int i, int j){
        
        // Base case
        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);
        }

        int option1 = LCS(s1, s2, i + 1, j);
        int option2 = LCS(s1, s2, i, j + 1);
        
        return Math.max(option1, option2);
    } 
    
    public static void main (String[] args){
         Scanner s = new Scanner(System.in);

         // Take Input
         System.out.println("Enter String1");
         String s1 = s.next();

         System.out.println("Enter String2");
         String s2 = s.next();

         int lcsans = LCS(s1,s2,0,0);

         System.out.println("Longest Common Subsequence "+ lcsans);
     }
}

You can also try this code with Online Java Compiler

Python

def LCS(s1, s2, i, j):
    # Base case
    if i == len(s1) or j == len(s2):
        return 0
    
    if s1[i] == s2[j]:
        return 1 + LCS(s1, s2, i + 1, j + 1)
    
    option1 = LCS(s1, s2, i + 1, j)
    option2 = LCS(s1, s2, i, j + 1)
    
    return max(option1, option2)

if __name__ == "__main__":
    s1 = input("Enter String1: ")
    s2 = input("Enter String2: ")
    
    lcsans = LCS(s1, s2, 0, 0)
    
    print("Longest Common Subsequence:", lcsans)

You can also try this code with Online Python Compiler

Javascript

function LCS(s1, s2, i, j) {
    // Base case
    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);
    }

    let option1 = LCS(s1, s2, i + 1, j);
    let option2 = LCS(s1, s2, i, j + 1);

    return Math.max(option1, option2);
}

function main() {
    const readline = require('readline');
    const rl = readline.createInterface({
        input: process.stdin,
        output: process.stdout
    });

    rl.question("Enter String1: ", function(s1) {
        rl.question("Enter String2: ", function(s2) {
            let lcsans = LCS(s1, s2, 0, 0);
            console.log("Longest Common Subsequence:", lcsans);
            rl.close();
        });
    });
}

main();

You can also try this code with Online Javascript Compiler

PHP

<?php
function LCS($s1, $s2, $i, $j) {
    // Base case
    if ($i == strlen($s1) || $j == strlen($s2)) return 0;

    if ($s1[$i] == $s2[$j]) {
        return 1 + LCS($s1, $s2, $i + 1, $j + 1);
    }

    $option1 = LCS($s1, $s2, $i + 1, $j);
    $option2 = LCS($s1, $s2, $i, $j + 1);

    return max($option1, $option2);
}

// Take Input
echo "Enter String1: ";
$s1 = readline();

echo "Enter String2: ";
$s2 = readline();

$lcsans = LCS($s1, $s2, 0, 0);

echo "Longest Common Subsequence: $lcsans\n";
?>

You can also try this code with Online PHP Compiler

C#

using System;

class Program {
    static int LCS(string s1, string s2, int i, int j) {
        // Base case
        if (i == s1.Length || j == s2.Length) return 0;

        if (s1[i] == s2[j]) {
            return 1 + LCS(s1, s2, i + 1, j + 1);
        }

        int option1 = LCS(s1, s2, i + 1, j);
        int option2 = LCS(s1, s2, i, j + 1);

        return Math.Max(option1, option2);
    }

    static void Main() {
        // Take Input
        Console.WriteLine("Enter String1: ");
        string s1 = Console.ReadLine();

        Console.WriteLine("Enter String2: ");
        string s2 = Console.ReadLine();

        int lcsans = LCS(s1, s2, 0, 0);

        Console.WriteLine("Longest Common Subsequence: " + lcsans);
    }
}

Output:

Enter String1 acbaed
Enter String2 abcadf
Longest Common Subsequence 4

Time and Space Complexity

Time Complexity: O(2 ^ N), i.e., exponential as we generate and compare all the subsequences of both the strings.

Note: The total number of subsequences of a string is O(2 ^ N).

Space Complexity: O(1) as no extra space is being used.

Where ‘N’ is the length of the shortest of the two strings.

Longest Common Subsequence (LCS) Using Dynamic Programming

We could optimize the time complexity of our previous approach by maintaining a “dp array” where - dp[i][j] stores the longest common subsequence value that could be formed via considering string1 till i-th index and string2 till jth index.

Let's look at the recursive tree:

Recursion Tree

Since the recursive approach had a lot of overlapping subproblems, the dp array would also help us avoid that repetitive work.

So, let’s consider the two strings “aggtab” and “gxtxayb.”

“-” here indicates that the value of LCS = 0 after considering the string1 and string2 till ith and jth index, respectively.

Every time a matching character is found, the LCS value increases by one else; it remains as it is.

1. Longest Common Subsequence (LCS) Using Top-Down Dp

Implementation

Let’s have a look at its implementation

C

#include <stdio.h>
#include <string.h>

int LCS(char s1[], char s2[], int m, int n, int dp[][100]) {
    // Base Case
    if (m <= 0 || n <= 0) return 0;

    // LookUp
    if (dp[m][n] != 0) return dp[m][n];

    // Calculating Longest Common Subsequence
    if (s1[m - 1] == s2[n - 1])
        dp[m][n] = LCS(s1, s2, m - 1, n - 1, dp) + 1;
    else
        dp[m][n] = (LCS(s1, s2, m - 1, n, dp) > LCS(s1, s2, m, n - 1, dp)) ? LCS(s1, s2, m - 1, n, dp) : LCS(s1, s2, m, n - 1, dp);

    return dp[m][n];
}

int main() {
    char s1[100], s2[100];

    // Take Input
    printf("Enter String1: ");
    scanf("%s", s1);

    printf("Enter String2: ");
    scanf("%s", s2);

    int m = strlen(s1);
    int n = strlen(s2);

    // Forming dp array
    int dp[101][101] = {0};

    int lcsans = LCS(s1, s2, m, n, dp);

    printf("Longest Common Subsequence: %d\n", lcsans);

    return 0;
}

You can also try this code with Online C Compiler

C++

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

int LCS(string s1, string s2, int m, int n, int dp[][101]) {
    // Base Case
    if (m <= 0 || n <= 0) return 0;

    // LookUp
    if (dp[m][n] != 0) return dp[m][n];

    // Calculating Longest Common Subsequence
    if (s1[m - 1] == s2[n - 1])
        dp[m][n] = LCS(s1, s2, m - 1, n - 1, dp) + 1;
    else
        dp[m][n] = max(LCS(s1, s2, m - 1, n, dp), LCS(s1, s2, m, n - 1, dp));

    return dp[m][n];
}

int main() {
    string s1, s2;

    // Take Input
    cout << "Enter String1: ";
    cin >> s1;

    cout << "Enter String2: ";
    cin >> s2;

    int m = s1.length();
    int n = s2.length();

    // Forming dp array
    int dp[101][101] = {0};

    int lcsans = LCS(s1, s2, m, n, dp);

    cout << "Longest Common Subsequence: " << lcsans << endl;

    return 0;
}

You can also try this code with Online C++ Compiler

Java

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Solution {
 
  // Using Top Down dp approach
    public static int LCS(String s1, String s2, int m, int n, int[][] dp){
        
        // Base Case
        if (m <= 0 || n <= 0) return 0;
 
        // LookUp
        if (dp[m][n] != 0) return dp[m][n];
        
        // Calculating Longest Common Subsequence
        if (s1.charAt(m) == s2.charAt(n))
            dp[m][n] = LCS(s1, s2, m - 1, n - 1, dp) + 1;
        else
            dp[m][n] = Math.max(LCS(s1, s2, m - 1, n, dp), LCS(s1, s2, m, n - 1, dp));
        
        
        return dp[m][n];
    } 
    
    public static void main (String[] args){
         Scanner s = new Scanner(System.in);
 
         // Take Input
         System.out.println("Enter String1");
         String s1 = s.next();
        
         System.out.println("Enter String2");
         String s2 = s.next();
        
         int m = s1.length();
         int n = s2.length();
    
         // Forming dp array
         int dp[][] = new int[m][n];
        
        int lcsans = LCS(s1, s2, m - 1, n - 1, dp);

        System.out.println("Longest Common Subsequence "+ lcsans);
   }
}

You can also try this code with Online Java Compiler

Python

def LCS(s1, s2, m, n, dp):
    # Base Case
    if m <= 0 or n <= 0:
        return 0

    # LookUp
    if dp[m][n] != 0:
        return dp[m][n]

    # Calculating Longest Common Subsequence
    if s1[m - 1] == s2[n - 1]:
        dp[m][n] = LCS(s1, s2, m - 1, n - 1, dp) + 1
    else:
        dp[m][n] = max(LCS(s1, s2, m - 1, n, dp), LCS(s1, s2, m, n - 1, dp))

    return dp[m][n]

if __name__ == "__main__":
    s1 = input("Enter String1: ")
    s2 = input("Enter String2: ")

    m = len(s1)
    n = len(s2)

    # Forming dp array
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    lcsans = LCS(s1, s2, m, n, dp)

    print("Longest Common Subsequence:", lcsans)

You can also try this code with Online Python Compiler

Javascript

function LCS(s1, s2, m, n, dp) {
    // Base Case
    if (m <= 0 || n <= 0) return 0;

    // LookUp
    if (dp[m][n] !== undefined) return dp[m][n];

    // Calculating Longest Common Subsequence
    if (s1.charAt(m - 1) === s2.charAt(n - 1)) {
        dp[m][n] = LCS(s1, s2, m - 1, n - 1, dp) + 1;
    } else {
        dp[m][n] = Math.max(LCS(s1, s2, m - 1, n, dp), LCS(s1, s2, m, n - 1, dp));
    }

    return dp[m][n];
}

function main() {
    const readline = require('readline');
    const rl = readline.createInterface({
        input: process.stdin,
        output: process.stdout
    });

    rl.question("Enter String1: ", function(s1) {
        rl.question("Enter String2: ", function(s2) {
            const m = s1.length;
            const n = s2.length;

            // Forming dp array
            let dp = new Array(m + 1).fill().map(() => new Array(n + 1));

            let lcsans = LCS(s1, s2, m, n, dp);

            console.log("Longest Common Subsequence:", lcsans);
            rl.close();
        });
    });
}

main();

You can also try this code with Online Javascript Compiler

PHP

<?php
function LCS($s1, $s2, $m, $n, &$dp) {
    // Base Case
    if ($m <= 0 || $n <= 0) return 0;

    // LookUp
    if (isset($dp[$m][$n])) return $dp[$m][$n];

    // Calculating Longest Common Subsequence
    if ($s1[$m - 1] == $s2[$n - 1]) {
        $dp[$m][$n] = LCS($s1, $s2, $m - 1, $n - 1, $dp) + 1;
    } else {
        $dp[$m][$n] = max(LCS($s1, $s2, $m - 1, $n, $dp), LCS($s1, $s2, $m, $n - 1, $dp));
    }

    return $dp[$m][$n];
}

// Take Input
echo "Enter String1: ";
$s1 = readline();

echo "Enter String2: ";
$s2 = readline();

$m = strlen($s1);
$n = strlen($s2);

// Forming dp array
$dp = array_fill(0, $m + 1, array_fill(0, $n + 1, 0));

$lcsans = LCS($s1, $s2, $m, $n, $dp);

echo "Longest Common Subsequence: $lcsans\n";
?>

You can also try this code with Online PHP Compiler

C#

using System;

class Program {
    static int LCS(string s1, string s2, int m, int n, int[,] dp) {
        // Base Case
        if (m <= 0 || n <= 0) return 0;

        // LookUp
        if (dp[m, n] != 0) return dp[m, n];

        // Calculating Longest Common Subsequence
        if (s1[m - 1] == s2[n - 1])
            dp[m, n] = LCS(s1, s2, m - 1, n - 1, dp) + 1;
        else
            dp[m, n] = Math.Max(LCS(s1, s2, m - 1, n, dp), LCS(s1, s2, m, n - 1, dp));

        return dp[m, n];
    }

    static void Main() {
        // Take Input
        Console.WriteLine("Enter String1: ");
        string s1 = Console.ReadLine();

        Console.WriteLine("Enter String2: ");
        string s2 = Console.ReadLine();

        int m = s1.Length;
        int n = s2.Length;

        // Forming dp array
        int[,] dp = new int[m + 1, n + 1];

        int lcsans = LCS(s1, s2, m, n, dp);

        Console.WriteLine("Longest Common Subsequence: " + lcsans);
    }
}

Output

Enter String1 acbaed
Enter String2 abcadf
Longest Common Subsequence 4

Time and Space Complexity

Time Complexity: O(N ^ 2) as for each length, we are traversing from 0 to that particular length to calculate our max possible profit for the current length.

Space Complexity: O(N ^ 2) as extra space is used to store the longest common subsequence value after considering both the strings until a particular index.

Where ‘N’ is the length of the shortest of the two strings.

2. Longest Common Subsequence (LCS) Using Bottom-Up Dp

Implementation

Let’s have a look at its implementation

C

#include <stdio.h>
#include <string.h>

int LCS(char s1[], char s2[]) {
    int m = strlen(s1);
    int n = strlen(s2);

    // Forming dp array
    int dp[m + 1][n + 1];

    // Calculating Longest Common Subsequence
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0)
                dp[i][j] = 0;
            else if (s1[i - 1] == s2[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = (dp[i - 1][j] > dp[i][j - 1]) ? dp[i - 1][j] : dp[i][j - 1];
        }
    }
    return dp[m][n];
}

int main() {
    char s1[100], s2[100];

    // Take Input
    printf("Enter String1: ");
    scanf("%s", s1);

    printf("Enter String2: ");
    scanf("%s", s2);

    int lcsans = LCS(s1, s2);

    printf("Longest Common Subsequence: %d\n", lcsans);

    return 0;
}

You can also try this code with Online C Compiler

C++

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

int LCS(string s1, string s2) {
    int m = s1.length();
    int n = s2.length();

    // Forming dp array
    int dp[m + 1][n + 1];

    // Calculating Longest Common Subsequence
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0)
                dp[i][j] = 0;
            else 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, s2;

    // Take Input
    cout << "Enter String1: ";
    cin >> s1;

    cout << "Enter String2: ";
    cin >> s2;

    int lcsans = LCS(s1, s2);

    cout << "Longest Common Subsequence: " << lcsans << endl;

    return 0;
}

You can also try this code with Online C++ Compiler

Java

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Solution {

  // Using dp approach
    public static int LCS(String s1, String s2){
        
        int m = s1.length();
        int n = s2.length();
    
        // Forming dp array
        int dp[][] = new int[m + 1][n + 1];
 
        // Calculating Longest Common Subsequence
        for (int i=0; i <= m; i++){
            for (int j=0; j <= n; j++){
                if (i == 0 || j == 0)
                    dp[i][j] = 0;
                
                /*
                  LCS length increases by one 
                    when there is a character match
                  */
                else 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];
    } 
    
    public static void main (String[] args){
Scanner s = new Scanner(System.in);

            // Take Input
System.out.println("Enter String1");
            String s1 = s.next();

            System.out.println("Enter String2");
            String s2 = s.next();

int lcsans = LCS(s1,s2);

System.out.println("Longest Common Subsequence "+ lcsans);
}
}

You can also try this code with Online Java Compiler

Python

def LCS(s1, s2):
    m = len(s1)
    n = len(s2)

    # Forming dp array
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # Calculating Longest Common Subsequence
    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 = input("Enter String1: ")
    s2 = input("Enter String2: ")

    lcsans = LCS(s1, s2)

    print("Longest Common Subsequence:", lcsans)

You can also try this code with Online Python Compiler

Javascript

function LCS(s1, s2) {
    let m = s1.length;
    let n = s2.length;

    // Forming dp array
    let dp = new Array(m + 1).fill().map(() => new Array(n + 1).fill(0));

    // Calculating Longest Common Subsequence
    for (let i = 1; i <= m; i++) {
        for (let 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];
}

function main() {
    const readline = require('readline');
    const rl = readline.createInterface({
        input: process.stdin,
        output: process.stdout
    });

    rl.question("Enter String1: ", function(s1) {
        rl.question("Enter String2: ", function(s2) {
            let lcsans = LCS(s1, s2);
            console.log("Longest Common Subsequence:", lcsans);
            rl.close();
        });
    });
}

main();

You can also try this code with Online Javascript Compiler

PHP

<?php
function LCS($s1, $s2) {
    $m = strlen($s1);
    $n = strlen($s2);

    // Forming dp array
    $dp = array_fill(0, $m + 1, array_fill(0, $n + 1, 0));

    // Calculating Longest Common Subsequence
    for ($i = 1; $i <= $m; $i++) {
        for ($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];
}

// Take Input
echo "Enter String1: ";
$s1 = readline();

echo "Enter String2: ";
$s2 = readline();

$lcsans = LCS($s1, $s2);

echo "Longest Common Subsequence: $lcsans\n";
?>

You can also try this code with Online PHP Compiler

C#

using System;

class Program {
    static int LCS(string s1, string s2) {
        int m = s1.Length;
        int n = s2.Length;

        // Forming dp array
        int[,] dp = new int[m + 1, n + 1];

        // Calculating Longest Common Subsequence
        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] = Math.Max(dp[i - 1, j], dp[i, j - 1]);
                }
            }
        }

        return dp[m, n];
    }

    static void Main() {
        // Take Input
        Console.WriteLine("Enter String1: ");
        string s1 = Console.ReadLine();

        Console.WriteLine("Enter String2: ");
        string s2 = Console.ReadLine();

        int lcsans = LCS(s1, s2);

        Console.WriteLine("Longest Common Subsequence: " + lcsans);
    }
}

Output:

Enter String1 acbaed
Enter String2 abcadf
Longest Common Subsequence 4

Time and Space Complexity

Time Complexity: O(N ^ 2) as for each length, we are traversing from 0 to that particular length to calculate our max possible profit for the current length.

Space Complexity: O(N ^ 2) as extra space is used to store the longest common subsequence value after considering both the strings until a particular index.

Where ‘N’ is the length of the shortest of the two strings.

Longest Common Subsequence Applications

The following are some applications of Longest common subsequence:-

1. Version Control Systems (e.g., Git)

2. DNA sequence comparison in bioinformatics

3. Text comparison and plagiarism detection

4. Data differencing and file synchronization

5. Natural Language Processing tasks like spell checkers and similarity analysis

Read about: LCS of 3 strings, Longest Common Substring

Frequently Asked Questions

What is meant by longest common subsequence?

The longest common subsequence (LCS) of two sequences is the longest sequence that appears in both sequences in the same order but not necessarily consecutively. It represents the maximum length of shared elements between the two sequences.

Why do we use LCS?

We use LCS to find similar parts within different sequences (text, code).

What are the conditions for LCS algorithm?

LCS works on any sequences, needing no specific order within the sequences.

What is the recursive formula for LCS?

If elements match, add 1 to LCS from shorter subsequences. Otherwise, take the maximum LCS from excluding either sequence's last element.

What is the longest common subsequence measure?

A measure of similarity between two sequences, indicating the length of the longest common subsequence (LCS) they share.

What is the longest common subsequence of an array?

The longest subsequence common to two or more arrays, representing elements appearing in the same order in each array.

What is the longest common subsequence in linear space?

Efficient algorithms like the Hunt–Szymanski algorithm achieve LCS computation with linear space complexity.

Conclusion

In this blog, we learned various approaches to the Longest Common Subsequence.

Longest Common Subsequence is a standard recursive problem that is optimized via Dynamic Programming.
A subsequence of a string is a new string generated from the original string with some (or none) characters deleted without changing the relative order of the remaining characters.
The optimized time complexity of this problem is O(N ^ 2) for each character at an index, and we are calculating and comparing the LCS value to the ith and jth index value of string1 and string2, respectively.

Live masterclass

Switch from non tech to high paying data analytics profile

by Alka Pandey, Data Scientist @ Hindustan Unilever

09 Oct, 2024

01:30 PM

117+ registered

Master PowerBI using Netflix Data

by Ashwin Goyal, Product @ HRS Group, Ex - Udaan, OYO

08 Oct, 2024

01:30 PM

584+ registered

Switch from non tech to high paying data analytics profile

by Alka Pandey, Data Scientist @ Hindustan Unilever

09 Oct, 2024

01:30 PM

117+ registered

Master PowerBI using Netflix Data

by Ashwin Goyal, Product @ HRS Group, Ex - Udaan, OYO

08 Oct, 2024

01:30 PM

584+ registered

View more events