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

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++ 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 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 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# 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 

<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> 

ACD

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