A Space Optimized Solution of LCS | C # Code for 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
using System ; class GFG { public static int lcs ( string X , string Y ) { int m = X . Length , n = Y . Length ; int [ , ] L = new int [ 2 , n + 1 ] ; int bi = 0 ; for ( int i = 0 ; i <= m ; i ++ ) { bi = i & 1 ; for ( int 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 ] ; } public static void Main ( ) { string X = " AGGTAB " ; string Y = " GXTXAYB " ; Console . Write ( " Length ▁ of ▁ LCS ▁ is ▁ " + lcs ( X , Y ) ) ; } }