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