Find the longest subsequence of a string that is a substring of another string

0 0 8 minutes read

Given two strings X and Y consisting of N and M characters, the task is to find the longest subsequence of a string X which is a substring of the string Y.

Examples:

Input: X = “ABCD”, Y = “ACDBDCD”
Output: ACD
Explanation:
“ACD” is longest subsequence of X which is substring of Y.

Input: X = A, Y = A
Output: A

Naive Approach: The simplest approach to solve the given problem is to find all the subsequences of the given string X and print that subsequence among all the generated subsequences which is of maximum length and is a substring of Y.

Time Complexity: O(N*M*2^N)
Auxiliary Space: O(N)

Efficient Approach: The above approach can also be optimized by using Dynamic Programming. The idea is to create a 2D array, dp[][] of dimensions (N + 1)*(M + 1) and the state dp[i][j] is maximum length of subsequence of X[0, i] which is substring of Y[0, j]. Follow the steps below to solve the problem:

Create a 2D array, dp[][] of size N+1 rows and M+1 columns.
Initialize the first row and the first column of the matrix with 0.
Fill all the remaining rows as follows:
- If the value of X[i – 1] is equal to the value of Y[j – 1], then update the value of dp[i][j] to (1 + dp[i – 1][j – 1]).
- Otherwise, update the value of dp[i][j] to dp[i – 1][j].
Store the maximum length of the required sequence in a variable len by iterating the last row in the matrix and store the row and column index of the maximum cell value in variables i and j respectively.
Create a variable, say res to store the resultant string and backtrack from the maximum cell value.
Iterate until the value of len is greater than 0, and perform the following steps:
- If the value of X[i – 1] is equal to the value of Y[j – 1], then append X[i – 1] to res and decrement the value of len, i and j by 1.
- Otherwise, decrement the value of i by 1.
After completing the above steps, print the string res as the result.

Below is the implementation of the above approach:

C++

// C++ program for the above approach 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the longest
// subsequence that matches with
// the substring of other string
string longestSubsequence(string X, string Y)
{
     
    // Stores the lengths of strings
    // X and Y
    int n = X.size();
    int m = Y.size();
 
    // Create a matrix
    vector<vector<int>> mat(n + 1, vector<int>(m + 1));
     
    // Initialize the matrix
    for(int i = 0; i < n + 1; i++) 
    {
        for(int j = 0; j < m + 1; j++) 
        {
            if (i == 0 || j == 0)
                mat[i][j] = 0;
        }
    }
 
    // Fill all the remaining rows
    for(int i = 1; i < n + 1; i++) 
    {
        for(int j = 1; j < m + 1; j++) 
        {
             
            // If the characters are equal
            if (X[i - 1] == Y[j - 1])
            {
                mat[i][j] = 1 + mat[i - 1][j - 1];
            }
 
            // If not equal, then
            // just move to next
            // in subsequence string
            else
            {
                mat[i][j] = mat[i - 1][j];
            }
        }
    }
 
    // Find maximum length of the
    // longest subsequence matching
    // substring of other string
    int len = 0, col = 0;
 
    // Iterate through the last
    // row of matrix
    for(int i = 0; i < m + 1; i++)
    {
        if (mat[n][i] > len)
        {
            len = mat[n][i];
            col = i;
        }
    }
 
    // Store the required string
    string res = "";
    int i = n;
    int j = col;
 
    // Backtrack from the cell
    while (len > 0) 
    {
         
        // If equal, then add the
        // character to res string
        if (X[i - 1] == Y[j - 1]) 
        {
            res = X[i - 1] + res;
            i--;
            j--;
            len--;
        }
        else
        {
            i--;
        }
    }
 
    // Return the required string
    return res;
}
 
// Driver code
int main()
{
    string X = "ABCD";
    string Y = "ACDBDCD";
     
    cout << (longestSubsequence(X, Y));
     
    return 0;
}
 
// This code is contributed by mohit kumar 29

Java

// Java program for the above approach
 
class GFG {
 
    // Function to find the longest
    // subsequence that matches with
    // the substring of other string
    public static String longestSubsequence(
        String X, String Y)
    {
 
        // Stores the lengths of strings
        // X and Y
        int n = X.length();
        int m = Y.length();
 
        // Create a matrix
        int[][] mat = new int[n + 1][m + 1];
 
        // Initialize the matrix
        for (int i = 0; i < n + 1; i++) {
            for (int j = 0; j < m + 1; j++) {
                if (i == 0 || j == 0)
                    mat[i][j] = 0;
            }
        }
 
        // Fill all the remaining rows
        for (int i = 1;
             i < n + 1; i++) {
 
            for (int j = 1;
                 j < m + 1; j++) {
 
                // If the characters are equal
                if (X.charAt(i - 1)
                    == Y.charAt(j - 1)) {
                    mat[i][j] = 1
                                + mat[i - 1][j - 1];
                }
 
                // If not equal, then
                // just move to next
                // in subsequence string
                else {
                    mat[i][j] = mat[i - 1][j];
                }
            }
        }
 
        // Find maximum length of the
        // longest subsequence matching
        // substring of other string
        int len = 0, col = 0;
 
        // Iterate through the last
        // row of matrix
        for (int i = 0; i < m + 1; i++) {
 
            if (mat[n][i] > len) {
                len = mat[n][i];
                col = i;
            }
        }
 
        // Store the required string
        String res = "";
        int i = n;
        int j = col;
 
        // Backtrack from the cell
        while (len > 0) {
 
            // If equal, then add the
            // character to res string
            if (X.charAt(i - 1)
                == Y.charAt(j - 1)) {
 
                res = X.charAt(i - 1) + res;
                i--;
                j--;
                len--;
            }
            else {
                i--;
            }
        }
 
        // Return the required string
        return res;
    }
 
    // Driver Code
    public static void main(String args[])
    {
        String X = "ABCD";
        String Y = "ACDBDCD";
        System.out.println(
            longestSubsequence(X, Y));
    }
}

Python3

# Python3 program for the above approach
 
# Function to find the longest
# subsequence that matches with
# the substring of other string
def longestSubsequence(X, Y):
     
    # Stores the lengths of strings
    # X and Y
    n = len(X)
    m = len(Y)
 
    # Create a matrix
    mat = [[0 for i in range(m + 1)] 
              for j in range(n + 1)]
               
    # Initialize the matrix
    for i in range(0, n + 1):
        for j in range(0, m + 1):
            if (i == 0 or j == 0):
                mat[i][j] = 0
 
    # Fill all the remaining rows
    for i in range(1, n + 1):
        for j in range(1, m + 1):
             
            # If the characters are equal
            if (X[i - 1] == Y[j - 1]):
                mat[i][j] = 1 + mat[i - 1][j - 1]
                 
            # If not equal, then
            # just move to next
            # in subsequence string
            else:
                mat[i][j] = mat[i - 1][j]
 
    # Find maximum length of the
    # longest subsequence matching
    # substring of other string
    len1 = 0
    col = 0
     
    # Iterate through the last
    # row of matrix
    for i in range(0, m + 1):
        if (mat[n][i] > len1):
            len1 = mat[n][i]
            col = i
 
    # Store the required string
    res = ""
    i = n
    j = col
     
    # Backtrack from the cell
    while (len1 > 0):
 
        # If equal, then add the
        # character to res string
        if (X[i - 1] == Y[j - 1]):
            res = X[i - 1] + res
            i -= 1
            j -= 1
            len1 -= 1
        else:
            i -= 1
 
    # Return the required string
    return res
 
# Driver code
X = "ABCD"
Y = "ACDBDCD"
 
print(longestSubsequence(X, Y))
 
# This code is contributed by amreshkumar3

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to find the longest
// subsequence that matches with
// the substring of other string
static string longestSubsequence(string X, string Y)
{
    int i, j;
     
    // Stores the lengths of strings
    // X and Y
    int n = X.Length;
    int m = Y.Length;
 
    // Create a matrix
    int [,]mat = new int[n + 1, m + 1];
 
    // Initialize the matrix
    for(i = 0; i < n + 1; i++) 
    {
        for(j = 0; j < m + 1; j++) 
        {
            if (i == 0 || j == 0)
                mat[i,j] = 0;
        }
    }
 
    // Fill all the remaining rows
    for(i = 1; i < n + 1; i++) 
    {
        for(j = 1; j < m + 1; j++)
        {
             
            // If the characters are equal
            if (X[i - 1] == Y[j - 1])
            {
                mat[i, j] = 1 + mat[i - 1, j - 1];
            }
 
            // If not equal, then
            // just move to next
            // in subsequence string
            else
            {
                mat[i, j] = mat[i - 1, j];
            }
        }
    }
 
    // Find maximum length of the
    // longest subsequence matching
    // substring of other string
    int len = 0, col = 0;
 
    // Iterate through the last
    // row of matrix
    for(i = 0; i < m + 1; i++) 
    {
        if (mat[n,i] > len)
        {
            len = mat[n,i];
            col = i;
        }
    }
 
    // Store the required string
    string res = "";
    i = n;
    j = col;
 
    // Backtrack from the cell
    while (len > 0)
    {
         
        // If equal, then add the
        // character to res string
        if (X[i - 1] == Y[j - 1]) 
        {
            res = X[i - 1] + res;
            i--;
            j--;
            len--;
        }
        else
        {
            i--;
        }
    }
 
    // Return the required string
    return res;
}
 
// Driver Code
public static void Main()
{
    string X = "ABCD";
    string Y = "ACDBDCD";
     
    Console.Write(longestSubsequence(X, Y));
}
}
 
// This code is contributed by bgangwar59

Javascript

<script>
 
// Javascript program for the above approach
 
// Function to find the longest
// subsequence that matches with
// the substring of other string
function longestSubsequence(X,Y)
{
        // Stores the lengths of strings
        // X and Y
        let n = X.length;
        let m = Y.length;
  
        // Create a matrix
        let mat = new Array(n + 1);
  
        // Initialize the matrix
        for (let i = 0; i < n + 1; i++) {
            mat[i]=new Array(m+1);
            for (let j = 0; j < m + 1; j++) {
                if (i == 0 || j == 0)
                    mat[i][j] = 0;
            }
        }
  
        // Fill all the remaining rows
        for (let i = 1;
             i < n + 1; i++) {
  
            for (let j = 1;
                 j < m + 1; j++) {
  
                // If the characters are equal
                if (X[i-1]
                    == Y[j-1]) {
                    mat[i][j] = 1
                                + mat[i - 1][j - 1];
                }
  
                // If not equal, then
                // just move to next
                // in subsequence string
                else {
                    mat[i][j] = mat[i - 1][j];
                }
            }
        }
  
        // Find maximum length of the
        // longest subsequence matching
        // substring of other string
        let len = 0, col = 0;
  
        // Iterate through the last
        // row of matrix
        for (let i = 0; i < m + 1; i++) {
  
            if (mat[n][i] > len) {
                len = mat[n][i];
                col = i;
            }
        }
  
        // Store the required string
        let res = "";
        let i = n;
        let j = col;
  
        // Backtrack from the cell
        while (len > 0) {
  
            // If equal, then add the
            // character to res string
            if (X[i-1]
                == Y[j-1]) {
  
                res = X[i-1] + res;
                i--;
                j--;
                len--;
            }
            else {
                i--;
            }
        }
  
        // Return the required string
        return res;
}
 
// Driver Code
let X = "ABCD";
let Y = "ACDBDCD";
document.write(longestSubsequence(X, Y));
 
 
// This code is contributed by unknown2108
</script>

Output:

ACD

Time Complexity: O(N*M)
Auxiliary Space: O(N*M)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!