A Space Optimized Solution of LCS | Returns length of LCS for X [ 0. . m - 1 ] , Y [ 0. . n - 1 ] ; Find lengths of two strings ; Binary index , used to index current row and previous row . ; Compute current binary index ; Last filled entry contains length of LCS for X [ 0. . n - 1 ] and Y [ 0. . m - 1 ] ; Driver code
function lcs ( X , Y ) { let m = X . length , n = Y . length ; let L = new Array ( 2 ) ; for ( let i = 0 ; i < 2 ; i ++ ) { L [ i ] = new Array ( n + 1 ) ; for ( let j = 0 ; j < n + 1 ; j ++ ) { L [ i ] [ j ] = 0 ; } } let bi = 0 ; for ( let i = 0 ; i <= m ; i ++ ) { bi = i & 1 ; for ( let j = 0 ; j <= n ; j ++ ) { if ( i == 0 j == 0 ) L [ bi ] [ j ] = 0 ; else if ( X [ i - 1 ] == Y [ j - 1 ] ) L [ bi ] [ j ] = L [ 1 - bi ] [ j - 1 ] + 1 ; else L [ bi ] [ j ] = Math . max ( L [ 1 - bi ] [ j ] , L [ bi ] [ j - 1 ] ) ; } } return L [ bi ] [ n ] ; } let X = " " ; let Y = " " ; document . write ( " " + lcs ( X , Y ) ) ;