title: Space Optimized Solution Lcs
signature: spaceOptimizedSolutionLcs :: String -> String -> Integer
  spaceOptimizedSolutionLcs x y = 
test_code: import Text.Printf
  import Control.Exception (catch, SomeException)
  import Data.Typeable
  import qualified Data.List as List
  import qualified Data.Map as Map
  import qualified Data.Set as Set
  
  -- SOLUTION CODE
  -- ============================================
  
  PLACEHOLDER_CODE_BODY
  
  -- TESTING CODE 
  -- ============================================
  validateSolution :: Integer -> Integer -> Bool
  validateSolution actual expected = do
      actual == expected
  
  
  driver :: String -> String -> Integer -> String
  driver x y expected = do
      if (validateSolution (PLACEHOLDER_FN_NAME x y) expected)
          then "PASSED"
      else "FAILED"
  
  main = do
      printf "TEST-0...%s\n" (driver ("YNpjSv") ("qtUkJn") (0) )
  
      printf "TEST-1...%s\n" (driver ("736519") ("07592") (2) )
  
      printf "TEST-2...%s\n" (driver ("11010000100010") ("0") (1) )
  
      printf "TEST-3...%s\n" (driver ("v ") ("qGBQT") (0) )
  
      printf "TEST-4...%s\n" (driver ("8311172") ("157219329531") (3) )
  
      printf "TEST-5...%s\n" (driver ("100011101011") ("1000001111") (7) )
  
      printf "TEST-6...%s\n" (driver ("u") ("YzkubTqLhP") (0) )
  
      printf "TEST-7...%s\n" (driver ("3943042") ("3859") (1) )
  
      printf "TEST-8...%s\n" (driver ("101") ("00010000101010") (2) )
  
      printf "TEST-9...%s\n" (driver ("MpbfF OsizevaM") ("WgsFGaQwtp") (2) )
  
source_py: def space_optimized_solution_lcs(X, Y):
      m = len(X)
      n = len(Y)
      L = [[0 for i in range((n + 1))] for j in range(2)]
      bi = bool
      for i in range(m):
          bi = (i & 1)
          for j in range((n + 1)):
              if ((i == 0) or (j == 0)):
                  L[bi][j] = 0
              elif (X[i] == Y[(j - 1)]):
                  L[bi][j] = (L[(1 - bi)][(j - 1)] + 1)
              else:
                  L[bi][j] = max(L[(1 - bi)][j], L[bi][(j - 1)])
      return L[bi][n]
source_cpp: int space_optimized_solution_lcs(string & X, string & Y) {
    int m = X . length ( ), n = Y . length ( );
    int L [ 2 ] [ n + 1 ];
    bool bi;
    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 ] = max ( L [ 1 - bi ] [ j ], L [ bi ] [ j - 1 ] );
      }
    }
    return L [ bi ] [ n ];
  }