To print the longest common subsequence

Solution:

public class Dsa {

    public static void main(String[] args) {

        String s1 = "ABCDAF";

        String s2 = "ACBCF";

        int lcsLength = LCS(s1, s2);

        System.out.println("Length of Longest Common Subsequence: " + lcsLength);

    }

    public static int LCS(String s1, String s2) {

        int n1 = s1.length();

        int n2 = s2.length();

        int dp[][] = new int[n1 + 1][n2 + 1];

        for (int i = 1; i <= n1; i++) {

            for (int j = 1; j <= n2; j++) {

                if (s1.charAt(i - 1) == s2.charAt(j - 1))

                    dp[i][j] = 1 + dp[i - 1][j - 1];

                else

                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);

            }

        }

        // to print lcs string

        int i = n1, j = n2;

        StringBuilder lcs = new StringBuilder();

        while (i > 0 && j > 0) {

            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {

                lcs.insert(0, s1.charAt(i - 1));

                i--;

                j--;

            } else if (dp[i - 1][j] > dp[i][j - 1]) {

                i--;

            } else {

                j--;

            }

        }

        System.out.println(lcs.toString());

        return dp[n1][n2]; //returns length of lcs string

    }

}