# Space Efficient LCSby Isai Damier, Android Engineer @ Google

```/***********************************************************************
* Author: Isai Damier
* Title: Longest Common Subsequence
* Project: geekviewpoint
* Package: algorithms
*
* Statement:
*   Given two sequences, find the longest common subsequence
*   between them.
*
*  Time Complexity: O(n*m)
*    where m and n are the size of the input arrays, respectively
*
* Sample Input: awaited, alpine
* Sample Output: aie
*
* DEFINITION OF SUBSEQUENCE:
*   A sequence is a particular order in which related objects follow
*   each other (e.g. DNA, Fibonacci). A sub-sequence is a sequence
*   obtained by omitting some of the elements of a larger sequence.
*
*   SEQUENCE       SUBSEQUENCE     OMISSION
*   {3,1,2,5,4}     {1,2}            3,5,4
*   {3,1,2,5,4}     {3,1,4}          2,5
*
*   SEQUENCE       NOT SUBSEQUENCE   REASON
*   {3,1,2,5,4}     {4,2,5}           4 should follow 5
*
* STRATEGY:
*   An easy way to find a longest common subsequence of characters between
*   two words is to first track the lengths of all the common sequences
*   and then from those lengths pick a maximum; finally, from that
*   maximum length, trace out the actual longest common subsequence
*   between the two words.
*
*   Let's use a table C (i.e. array C) to track the lengths of all common
*   sub-sequences between the two input words. Naturally, C starts with
*   all cells set to zero. Then to fill up C, we walk thru the two words,
*   comparing characters. Each time we find a match, we mark the
*   corresponding cell in C as one plus whatever maximum we had seen so
*   far for that particular sub-sequence.
*
*   When we are done filling up C, we find a maximum length z in C. Then
*   using the indices of z, we trace that actual sequence and return it
*
*   The ensuing code shows the details of how we fill C and then from C
*   extract the actual LCS.
*
*          ~~~~    ~~~~    ~~~~    ~~~~    ~~~~    ~~~~    ~~~~
*
*   The remaining paragraphs contain details that you may not particularly
*   care for. You may skip them and go right to the code.
*
*   Finding the LCS of two sequences X and Y, i.e. LCS(X,Y), is similar
*   in structure to finding the Fibonacci of some number n, i.e. fib(n).
*   Both problems exhibit optimal substructures. Which is to say,
*   for instance, the solution to fib(5) contains the solution to fib(4)
*   which in turn contains fib(3), and so on. Similarly, the solution
*   of LCS(X,Y) contains the solution of LCS(X-1,Y), which in turn
*   contains the solution of LCS(X-1,Y-1), and so on. Whenever a problem
*   exhibits "optimal substructure", we can use recursion to solve it:
*
*               _
*              | fib(n-1)+fib(n-2)    if n > 1
*     fib(n) = | n                    if n == 1 or n == 0
*              |_
*
*   For the LCS recurrence relation, a few notes are necessary:
*   Let C(i,j) be the length of the prefix of LCS(X,Y) given by
*
*     C(i,j) = |LCS(X[1..i],Y[1..j])|
*
*   so that if the length of X is m and the length of Y is n,
*
*     C(m,n) = |LCS(X,Y)|
*
*   Then the recurrence relation for filling C is
*               _
*              | C(i-1,j-1)+1            if X(i) == Y(j)
*     C(i,j) = | max{C(i-1,j),C(i,j-1)}  otherwise
*              |_
*
*   In addition to "optimal substructures", the LCS(X,Y) like the fib(n)
*   contains overlapping subproblems.  What we mean is this: In solving
*   f(5), we meet f(2) both as a subproblem of f(4) and as a subproblem
*   of f(3).
*
*               fib(5)
*             /        \
*         fib(4)        fib(3)       :fib(5)=fib(4)+fib(3)
*         /    \       /     \
*     fib(3) fib(2)  fib(2)  fib(1)  :fib(5)=fib(3)+fib(2)+fib(2)+fib(1)
*
*   Whenever a problem exhibits "overlapping subproblems", if you use
*   recursion as a strategy you will end up solving the same subproblems
*   more than once. Therefore, it makes more sense to track subproblems
*   using a table so that once you solve a subproblem, you can simply
*   lookup it's solution next time you need.
*
* CONCLUSION:
*   In the foregoing "strategy" section, we essentially described
*   dynamic programming.
*
*   Dynamic Programming: (aka Dynamic Tabling) is a strategy for solving
*     problems, which exhibit optimal substructures and overlapping
*     subproblems, by using a table to track the solution of subproblems
*     that have already been solved so as not to solve a subproblem more
*     than once. This tracking or note taking is usually referred to as
*     memoization, meaning writing in a memo.
*
**********************************************************************/
package algorithm.programming.dynamic;

public class LongestCommonSubsequence {

/********************************************************************
*  Space Complexity: O(min(n,m))
*    where m and n are the size of the input arrays, respectively.
*
* There are a number of reduced space LCS algorithms. This is just
* one approach.
********************************************************************/
public int spaceEfficientLCS_length(int[] A, int[] B) {
if (A.length > B.length) {
return LCS_length(A, B);
}
return LCS_length(B, A);
}

private int LCS_length(int[] B, int[] A) {
int m = A.length, n = B.length;
int[][] T = new int[n + 1];

for (int i = m - 1; i >= 0; i--) {
int ndx = i & 1;//odd or even
for (int j = n - 1; j >= 0; j--) {
if (A[i] == B[j]) {
T[ndx][j] = 1 + T[1 - ndx][j + 1];
} else {
T[ndx][j] = Math.max(T[1 - ndx][j], T[ndx][j + 1]);
}
}
}
return T;
}
}```
```package algorithm.programming.dynamic;

import java.util.Arrays;
import java.util.List;
import org.junit.Test;
import static org.junit.Assert.*;

public class LongestCommonSubsequenceTest {

/**
* Test of LCS method, of class LongestCommonSubsequence.
*/
@Test
public void testSpaceEfficientLCS_length() {
System.out.println("spaceEfficientLCS_length");
int[] fibonacci = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,
144, 233, 377, 610, 987};
int[] prime = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,
101, 103};
int[] rand = {0, 1, 21, 45, 144, 610, 987};
int[] bad = {102, 104, 106, 108, 110, 112, 114};

int exp1 = 5;
int exp2 = 6;

//no shared end points
LongestCommonSubsequence seq = new LongestCommonSubsequence();
int actual = seq.spaceEfficientLCS_length(fibonacci, prime);
assertEquals(exp1, actual);

//share both end points
actual = seq.spaceEfficientLCS_length(fibonacci, rand);
assertEquals(exp2, actual);

//share no points