# Find the Longest Common Subsequence in Java

## The challenge

from Wikipedia:

The longest common subsequence (LCS) problem is the problem of finding the longest subsequence common to all sequences in a set of sequences.

It differs from problems of finding common substrings: unlike substrings, subsequences are not required to occupy consecutive positions within the original sequences.

### Task

Write a function `lcs`

that accepts two `string`

s and returns their longest common subsequence as a `string`

. Performance matters.

### Examples

```
lcs( "abcdef", "abc" ) => "abc"
lcs( "abcdef", "acf" ) => "acf"
lcs( "132535365", "123456789" ) => "12356"
lcs( "abcdefghijklmnopq", "apcdefghijklmnobq" ) => "acdefghijklmnoq"
```

### Notes

The subsequences of `"abc"`

are `"", "a", "b", "c", "ab", "ac", "bc", "abc"`

.`""`

is a valid subsequence in this challenge, and a possible return value.

All inputs will be valid.

Two strings may have more than one longest common subsequence. When this occurs, return any of them.

```
lcs( string0, string1 ) === lcs( string1, string0 )
```

## The solution in Java code

Option 1:

```
class Lcs {
static String lcs(String a, String b) {
return backtrack(buildDistanceArray(a, b), a, b, a.length(), b.length());
}
private static int[][] buildDistanceArray(String s1, String s2){
int[][] returnArray = new int[s1.length() + 1][s2.length() + 1];
for(int i = 1; i <= s1.length(); i++){
for (int j = 1; j <= s2.length(); j++){
returnArray[i][j] = (s1.charAt(i - 1) == s2.charAt(j - 1)) ?
returnArray[i-1][j-1] + 1:
Math.max(returnArray[i][j-1], returnArray[i-1][j]);
}
}
return returnArray;
}
private static String backtrack(int[][] distArray, String s1, String s2, int i, int j){
if(i * j == 0) return "";
if(s1.charAt(i - 1) == s2.charAt(j - 1)) return backtrack(distArray, s1, s2, i-1, j-1) + s1.charAt(i - 1);
if (distArray[i][j-1] > distArray[i-1][j]) return backtrack(distArray, s1, s2, i, j-1);
return backtrack(distArray, s1, s2, i-1, j);
}
}
```

Option 2:

```
class Lcs {
public static String lcs(String x, String y) {
if (x.length() == 0 || y.length() == 0 || x == null || y == null)
return "";
String MaxResult = "";
String result = "";
for (int i = 0; i < x.length(); i++) {
String currRes = x.substring(i, i+1);
int posRes = y.indexOf(currRes);
if (posRes >= 0) {
result = currRes+lcs(x.substring(i+1),y.substring(posRes+1));
}
if (result.length() > MaxResult.length()) {MaxResult = result;}
}
return MaxResult;
}
}
```

Option 3:

```
class Lcs {
static String lcs(String a, String b) {
int[][] matrix = new int[a.length() + 1][b.length() + 1];
for(int i=1; i <= a.length(); i++){
for(int j=1; j <= b.length(); j++){
if(a.charAt(i-1) == b.charAt(j-1)){
matrix[i][j] = matrix[i-1][j-1] + 1;
}else{
matrix[i][j] = Math.max(matrix[i-1][j], matrix[i][j-1]);
}
}
}
StringBuilder seq = new StringBuilder();
int i, j;
i = a.length();
j = b.length();
while(i > 0 && j > 0){
if(a.charAt(i-1) == b.charAt(j-1)){
seq.append(b.charAt(j-1));
i--;
j--;
}else{
if(matrix[i-1][j] > matrix[i][j-1]){
i--;
}else
j--;
}
}
String out = seq.reverse().toString();
return out; // do it!
}
}
```

## Test cases to validate our solution

```
import org.junit.Test;
import java.util.Arrays;
import java.util.Random;
import static org.junit.Assert.assertEquals;
public class LcsTest {
@Test
public void fixedTests() {
assertEquals("", Lcs.lcs("", ""));
assertEquals("", Lcs.lcs("abc", ""));
assertEquals("", Lcs.lcs("", "abc"));
assertEquals("", Lcs.lcs("a", "b"));
assertEquals("a", Lcs.lcs("a", "a"));
assertEquals("ac", Lcs.lcs("abc", "ac"));
assertEquals("abc", Lcs.lcs("abcdef", "abc"));
assertEquals("acf", Lcs.lcs("abcdef", "acf"));
assertEquals("nottest", Lcs.lcs("anothertest", "notatest"));
assertEquals("12356", Lcs.lcs("132535365", "123456789"));
assertEquals("final", Lcs.lcs("nothardlythefinaltest", "zzzfinallyzzz"));
assertEquals("acdefghijklmnoq", Lcs.lcs("abcdefghijklmnopq", "apcdefghijklmnobq"));
}
}
```