Longest common subsequence Program in Java

To write a Java method lcs that recursively processes two strings from the back and returns the longest common suffix, you can use the following approach:

If either of the strings is empty, return an empty string.

If the last characters of the strings are equal, add the last character to the result and call the function recursively with the strings without their last characters.

If the last characters are not equal, call the function recursively with the first string and the second string without its last character, and with the second string and the first string without its last character. Return the longer of the two resulting strings.

Here is an example of how you could implement this in Java:

class StringUtils {

  public static String lcs(String s1, String s2) {

    if (s1.isEmpty() || s2.isEmpty()) {

      return "";

    }

    if (s1.charAt(s1.length() - 1) == s2.charAt(s2.length() - 1)) {

      return s1.charAt(s1.length() - 1) + lcs(s1.substring(0, s1.length() - 1), s2.substring(0, s2.length() - 1));

    }

    String s1s2 = lcs(s1, s2.substring(0, s2.length() - 1));

    String s2s1 = lcs(s1.substring(0, s1.length() - 1), s2);

    return s1s2.length() > s2s1.length() ? s1s2 : s2s1;

  }

}

You can then call the lcs method as follows:

String s1 = "abcdef";

String s2 = "abcghijklmdef";

String lcs = StringUtils.lcs(s1, s2);

System.out.println(lcs); // Outputs "def"