LCS

import java.util.Arrays;

public class LCS {

    public static void main(String[] args) {
        String str1 = "FAGGTAB";
        String str2 = "FGXTXAYB";

        int[][] matrix = buildMatrix(str1, str2);

        for (int[] ints : matrix) {
            System.out.println(Arrays.toString(ints));
        }

        String result = assemble(str1, str2, matrix, str1.length(), str2.length());

        System.out.println("result [" + result + "]");
    }

    private static String assemble(String str1, String str2, int[][] matrix, int i, int j) {
        if (matrix[i][j] == 0) {
            return "";
        }
        int nextIIndex = i - 1;
        int nextJIndex = j - 1;

        char thisIChar = str1.toCharArray()[nextIIndex];
        char thisJChar = str2.toCharArray()[nextJIndex];

        if (thisIChar == thisJChar) {
            return assemble(str1, str2, matrix, nextIIndex, nextJIndex) + thisIChar;
        }
        int lastI = matrix[nextIIndex][j];
        int lastJ = matrix[i][nextJIndex];
        if (lastI >= lastJ) {
            return assemble(str1, str2, matrix, nextIIndex, j);
        } else {
            return assemble(str1, str2, matrix, i, nextJIndex);
        }
    }

    private static int[][] buildMatrix(String str1, String str2) {

        int[][] res = new int[str1.length() + 1][str2.length() + 1];

        char[] c1 = str1.toCharArray();
        char[] c2 = str2.toCharArray();
        for (int i = 0; i < c1.length + 1; i++) {
            if (i == 0)
                continue;
            for (int j = 0; j < c2.length + 1; j++) {
                if (j == 0)
                    continue;
                if (c1[i - 1] == c2[j - 1]) {
                    res[i][j] = res[i - 1][j - 1] + 1;
                } else {
                    res[i][j] = Math.max(res[i][j - 1], res[i - 1][j]);
                }
            }
        }


        return res;
    }
}