Java - LCS of three strings

Java Code:

public class LCSofThreeStrings {

    // Function to find the LCS of three strings

    public static int LCSofThreeStrings(String str1, String str2, String str3) {

        int m = str1.length();

        int n = str2.length();

        int o = str3.length();

        // Create a 3D DP table to store lengths of LCS of substrings

        int[][][] dp = new int[m + 1][n + 1][o + 1];

        // Fill the DP table

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

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

                for (int k = 1; k <= o; k++) {

                    // If characters match in all three strings

                    if (str1.charAt(i - 1) == str2.charAt(j - 1) && str2.charAt(j - 1) == str3.charAt(k - 1)) {

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

                    } else {

                        // Take the maximum from the previous subproblems

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

                    }

                }

            }

        }

        // The length of LCS of the three strings is stored in dp[m][n][o]

        return dp[m][n][o];

    }

    public static void main(String[] args) {

        // Example strings

        String str1 = "AGGT12";

        String str2 = "12TXAYB";

        String str3 = "12XBA";

        // Find and print the length of LCS of the three strings

        int result = LCSofThreeStrings(str1, str2, str3);

        System.out.println("Length of LCS of three strings: " + result);

    }

}

Explanation:

3D DP Table: The 3D DP table dp[i][j][k] represents the length of the LCS of the first i characters of str1, the first j characters of str2, and the first k characters of str3.

Base Case: If any of the strings has zero length (i == 0, j == 0, or k == 0), then the LCS is 0. Thus, all entries in the table are initialized to 0.

Filling the DP Table:

If the characters of all three strings match (str1.charAt(i-1) == str2.charAt(j-1) == str3.charAt(k-1)), we increment the LCS length: dp[i][j][k] = dp[i-1][j-1][k-1] + 1.

Otherwise, we take the maximum of the LCS values from the subproblems:

)

dp[i][j][k]=max(dp[i−1][j][k],dp[i][j−1][k],dp[i][j][k−1])

Final Answer: The length of the LCS of the three strings is stored in dp[m][n][o], where m, n, and o are the lengths of the three input strings.

Example Output:

For the input strings "AGGT12", "12TXAYB", and "12XBA", the output will be:

Length of LCS of three strings: 3