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*2N)
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 stringstring 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 codeint 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 approachclass 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 stringdef 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 codeX = "ABCD"Y = "ACDBDCD"print(longestSubsequence(X, Y))# This code is contributed by amreshkumar3 |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function to find the longest// subsequence that matches with// the substring of other stringstatic 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 Codepublic 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 stringfunction 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 Codelet 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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
