Longest Common Subsequence (Performance version)

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

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

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

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

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;
  }
  
  

}

import java.util.Arrays;
import java.util.List;
import java.util.concurrent.atomic.AtomicInteger;

public class Lcs {

    static String lcs(String a, String b) {
        List<String> lower = a.length() > b.length() ? Arrays.asList(b.split("")) : Arrays.asList(a.split(""));
        List<String> bigger = a.length() <= b.length() ? Arrays.asList(b.split("")) : Arrays.asList(a.split(""));
        return lcs_recursion(lower, bigger);// do it!
    }

    public static String lcs_recursion(List<String> lower, List<String> bigger) {
        AtomicInteger lowerIndex = new AtomicInteger(Integer.MAX_VALUE);
        final String[] result = {""};
        lower.forEach(item -> {
            if (bigger.contains(item) && bigger.indexOf(item)< lowerIndex.get()) {
                lowerIndex.set(bigger.indexOf(item));
                String res = lcs_recursion(lower.subList(lower.indexOf(item)+1, lower.size()), bigger.subList(bigger.indexOf(item)+1, bigger.size()));
                result[0] = res.length() + 1> result[0].length() ? item + res : result[0];
            }
        });
        return result[0];
    }

}

class Lcs {

  static String lcs(String a, String b) {
    char[] X = a.toCharArray();
    char[] Y = b.toCharArray();
    int m = X.length;
    int n = Y.length;
    int L[][] = new int[m + 1][n + 1];

    for ( int i = 0; i <= m; i++ ) {
      for ( int j = 0; j <= n; j++ ) {
        if ( i == 0 || j == 0 ) {
          L[i][j] = 0;
        }
        else if ( X[i - 1] == Y[j - 1] ) {
          L[i][j] = L[i - 1][j - 1] + 1;
        }
        else {
          L[i][j] = Math.max( L[i - 1][j], L[i][j - 1] );
        }
      }
    }

    int index = L[m][n];

    StringBuilder sb = new StringBuilder( index );

    int i = m, j = n;
    while ( i > 0 && j > 0 ) {
      if ( X[i - 1] == Y[j - 1] ) {
        sb.append( X[i - 1] );

        i--;
        j--;
        index--;
      }
      else if ( L[i - 1][j] > L[i][j - 1] ) {
        i--;
      }
      else {
        j--;
      }
    }

    return sb.reverse().toString();
  }

}

class Lcs {

  static String lcs(String a, String b) {
    if(a.length() == 0 || b.length() == 0){
      return "";
    }
    if(a.equals(b)){
      return a;
    }
    
    char[] arrA = a.toCharArray();
    char[] arrB = b.toCharArray();
    
    
    int startIndex = 1;
    int lengthA = arrA.length + 1; // + 1 since the first row and cols = 0 length.
    int lengthB = arrB.length + 1;
    
    int[][] path = new int[lengthA][lengthB];
    // Create "path" that tracks the longest
    // subsequence calculated from each character.
    // The end of the "path" will be the longest 
    // common subsequence length.
    for(int i = startIndex; i < lengthA; i++){
      for(int j = startIndex; j < lengthB; j++){
        if(arrA[i - 1] == arrB[j - 1]){
          // Matching character.
          path[i][j] = path[i - 1][j - 1] + 1;
        } else {
          // Find the longest common subsequence length
          // and continue from that subsequence.
          int left = path[i - 1][j];
          int above = path[i][j - 1];
          path[i][j] = left > above? left:above;
        }
      }
    }
    // From the end of the path, 
    // backtrack and print the longest common subsequence
    return getLcs(path, arrA, arrB, lengthA - 1, lengthB - 1);
  }
  
  private static String getLcs(int[][] path, char[] a, char[] b, int i, int j){
    if(i == 0 || j == 0){
      // Root of subsequence.
      return "";
    }else if(a[i - 1] == b[j - 1]){
      // Matching character, append and move diagonally up.
      return getLcs(path, a, b, i - 1, j - 1) + a[i - 1];
    }else if(path[i][j - 1] > path[i - 1][j]){
      // above has greater length, backtrack to above.
      return getLcs(path, a, b, i, j - 1);
    }else{
      // backtrack to the left.
      return getLcs(path, a, b, i - 1, j);
    }
  }
  
}