Print Longest Palindromic Subsequence | Returns LCS X and Y ; Following steps build L [ m + 1 ] [ n + 1 ] in bottom up fashion . Note that L [ i ] [ j ] contains length of LCS of X [ 0. . i - 1 ] and Y [ 0. . j - 1 ] ; Following code is used to print LCS ; Create a String length index + 1 and fill it with \ 0 ; Start from the right - most - bottom - most corner and one by one store characters in lcs [ ] ; If current character in X [ ] and Y are same , then current character is part of LCS ; Put current character in result ; reduce values of i , j and index ; } If not same , then find the larger of two and go in the direction of larger value ; Returns longest palindromic subsequence of str ; Find reverse of str ; Return LCS of str and its reverse ; convert String to character array by using toCharArray ; Driver program to test above function
function lcs ( a , b ) { let m = a . length ; let n = b . length ; let X = a . split ( ' ' ) ; let Y = b . split ( ' ' ) ; let L = new Array ( m + 1 ) ; for ( let i = 0 ; i <= m ; i ++ ) { L [ i ] = new Array ( n + 1 ) ; for ( let j = 0 ; j <= n ; j ++ ) { L [ i ] [ j ] = 0 ; } } for ( let i = 0 ; i <= m ; i ++ ) { for ( let j = 0 ; j <= n ; j ++ ) { if ( i == 0 j == 0 ) { L [ i ] [ j ] = 0 ; } else if ( X [ i - 1 ] == Y [ j - 1 ] ) { L [ i ] [ j ] = L [ i - 1 ] [ j - 1 ] + 1 ; } else { L [ i ] [ j ] = Math . max ( L [ i - 1 ] [ j ] , L [ i ] [ j - 1 ] ) ; } } } let index = L [ m ] [ n ] ; let lcs = new Array ( index + 1 ) ; lcs . fill ( ' ' ) ; let i = m , j = n ; while ( i > 0 && j > 0 ) { if ( X [ i - 1 ] == Y [ j - 1 ] ) { lcs [ index - 1 ] = X [ i - 1 ] ; i -- ; j -- ; index -- ; else if ( L [ i - 1 ] [ j ] > L [ i ] [ j - 1 ] ) { i -- ; } else { j -- ; } } let ans = " " ; for ( let x = 0 ; x < lcs . length ; x ++ ) { ans += lcs [ x ] ; } return ans ; } function longestPalSubseq ( str ) { let rev = str ; rev = reverse ( rev ) ; return lcs ( str , rev ) ; } function reverse ( str ) { let ans = " " ; let try1 = str . split ( ' ' ) ; for ( let i = try1 . length - 1 ; i >= 0 ; i -- ) { ans += try1 [ i ] ; } return ans ; } let str = " " ; document . write ( longestPalSubseq ( str ) ) ;