Longest Common Subsequence in Java

Problem : Given two sequences, find the longest subsequence present in both of them. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous.(Reference GeekForGeeks).
LCS for input Sequences “ABCDGH” and “AEDFHR” is “ADH” of length 3.
LCS for input Sequences “AGGTAB” and “GXTXAYB” is “GTAB” of length 4.

Solution using Recursion:- Order of 2ⁿ

static public int LCSRecursiveSolution(char[] arr1, char[] arr2, int m,
		int n) {
	if (m == 0 || n == 0) {
		return 0;
	}
	if (arr1[m - 1] == arr2[n - 1]) {
		return 1 + LCSRecursiveSolution(arr1, arr2, m - 1, n - 1);
	}
	return Math.max(LCSRecursiveSolution(arr1, arr2, m, n - 1),
			LCSRecursiveSolution(arr1, arr2, m - 1, n));
}

Using dynamic programming :-

static public int LCSUsingDynamicProgramming(char[] arr1, char[] arr2,
		int m, int n) {
	int[][] solution = new int[m + 1][n + 1];
	for (int i = 0; i < m; i++) {
		solution[0][i] = 0;
	}
	for (int i = 0; i < n; i++) {
		solution[i][0] = 0;
	}

	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			if (arr1[i - 1] == arr2[j - 1]) {
				solution[i][j] = solution[i - 1][j - 1] + 1;
			} else {
				solution[i][j] = Math.max(solution[i - 1][j],
						solution[i][j - 1]);
			}
		}
	}
	printLCS(solution, arr1, arr2, m, n);
	return solution[m][n];
}

Display longest common subsequence:-

static void printLCS(int[][] solution, char[] arr1, char[] arr2, int m,
		int n) {
	int i = m;
	int j = n;
	int index = 0;
	char[] result = new char[solution[m][n]];
	
	while (i > 0 && j > 0) {
		if (arr1[i - 1] == arr2[j - 1]) {
			result[index] = arr1[i-1];
			i--;
			j--;
			index++;
		} else if (solution[i][j - 1] > solution[i - 1][j]) {
			j = j - 1;
		} else {
			i = i - 1;
		}
	}
	System.out.println(result);
}

Complete sample program :-

package com.ds.dp;

public class LCSUsingDP {

public static void main(String[] args) {
	char X[] = "AGGTAB".toCharArray();
	char Y[] = "GXTXAYB".toCharArray();
	// System.out.println(LCSRecursiveSolution(X, Y, X.length, Y.length));
	System.out.println("Length of lcs is: "
			+ LCSUsingDynamicProgramming(X, Y, X.length, Y.length));

}

static public int LCSRecursiveSolution(char[] arr1, char[] arr2, int m,
		int n) {
	if (m == 0 || n == 0) {
		return 0;
	}
	if (arr1[m - 1] == arr2[n - 1]) {
		return 1 + LCSRecursiveSolution(arr1, arr2, m - 1, n - 1);
	}
	return Math.max(LCSRecursiveSolution(arr1, arr2, m, n - 1),
			LCSRecursiveSolution(arr1, arr2, m - 1, n));
}

static public int LCSUsingDynamicProgramming(char[] arr1, char[] arr2,
		int m, int n) {
	int[][] solution = new int[m + 1][n + 1];
	for (int i = 0; i < m; i++) {
		solution[0][i] = 0;
	}
	for (int i = 0; i < n; i++) {
		solution[i][0] = 0;
	}

	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			if (arr1[i - 1] == arr2[j - 1]) {
				solution[i][j] = solution[i - 1][j - 1] + 1;
			} else {
				solution[i][j] = Math.max(solution[i - 1][j],
						solution[i][j - 1]);
			}
		}
	}
	printLCS(solution, arr1, arr2, m, n);
	return solution[m][n];
}

static void printLCS(int[][] solution, char[] arr1, char[] arr2, int m,
		int n) {
	int i = m;
	int j = n;
	int index = 0;
	char[] result = new char[solution[m][n]];

	while (i > 0 && j > 0) {
		if (arr1[i - 1] == arr2[j - 1]) {
			result[index] = arr1[i - 1];
			i--;
			j--;
			index++;
		} else if (solution[i][j - 1] > solution[i - 1][j]) {
			j = j - 1;
		} else {
			i = i - 1;
		}
	}
	System.out.print("longest lcs: ");
	System.out.println(result);
}
}

Sample output:-
longest lcs: BATG
Length of lcs is: 4