Longest Common Subsequence: DP Deep Dive With Real Examples

public class LCSTableBuilder {

    /**
     * Builds the full DP table for LCS and prints it so you can
     * visually trace exactly what the algorithm is doing.
     *
     * @param text1  First input sequence
     * @param text2  Second input sequence
     * @return       Length of the Longest Common Subsequence
     */
    public static int buildAndPrintTable(String text1, String text2) {
        int rows = text1.length();
        int cols = text2.length();

        // dp[i][j] = LCS length of text1[0..i-1] and text2[0..j-1]
        // We allocate (rows+1) x (cols+1) to naturally handle the base case:
        // row 0 and col 0 are all zeros — empty prefix has LCS of 0 with anything.
        int[][] dp = new int[rows + 1][cols + 1];

        // Fill table bottom-up: row by row, left to right
        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    // Characters match — extend the LCS found without these two chars
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    // No match — best we can do is skip one character from either string
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        // Print the table with headers for readability
        System.out.println("\nDP Table (rows = '" + text1 + "', cols = '" + text2 + "'):");
        System.out.print("    "); // top-left corner padding
        System.out.print("  ε "); // ε represents the empty string base case
        for (char c : text2.toCharArray()) {
            System.out.printf(" %c ", c);
        }
        System.out.println();

        for (int i = 0; i <= rows; i++) {
            // Row label: ε for base row, otherwise the current character
            if (i == 0) System.out.print("  ε ");
            else        System.out.printf("  %c ", text1.charAt(i - 1));

            for (int j = 0; j <= cols; j++) {
                System.out.printf(" %d ", dp[i][j]);
            }
            System.out.println();
        }

        int lcsLength = dp[rows][cols];
        System.out.println("\nLCS Length: " + lcsLength);
        return lcsLength;
    }

    public static void main(String[] args) {
        buildAndPrintTable("AGCAT", "GAC");
    }
}

public class LCSReconstructor {

    /**
     * Returns the actual LCS string (not just its length) by building
     * the DP table and then backtracking through it.
     *
     * Time:  O(m * n) for table fill + O(m + n) for backtracking
     * Space: O(m * n) for the table
     */
    public static String findLCS(String text1, String text2) {
        int rows = text1.length();
        int cols = text2.length();
        int[][] dp = new int[rows + 1][cols + 1];

        // --- Phase 1: Fill the DP table (identical to the basic version) ---
        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        // --- Phase 2: Backtrack from dp[rows][cols] to dp[0][0] ---
        StringBuilder lcsReversed = new StringBuilder();
        int i = rows;
        int j = cols;

        while (i > 0 && j > 0) {
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                // This character is part of the LCS — record it and go diagonal
                lcsReversed.append(text1.charAt(i - 1));
                i--;
                j--;
            } else if (dp[i - 1][j] >= dp[i][j - 1]) {
                // Moving up was at least as good — skip text1's character
                i--;
            } else {
                // Moving left was better — skip text2's character
                j--;
            }
        }

        // Characters were added in reverse order during backtracking
        return lcsReversed.reverse().toString();
    }

    public static void main(String[] args) {
        String sequence1 = "ABCBDAB";
        String sequence2 = "BDCAB";

        String lcs = findLCS(sequence1, sequence2);

        System.out.println("Sequence 1 : " + sequence1);
        System.out.println("Sequence 2 : " + sequence2);
        System.out.println("LCS        : " + lcs);
        System.out.println("LCS Length : " + lcs.length());

        // Demonstrate non-uniqueness: a different valid LCS also exists
        System.out.println("\nNote: 'BCAB' is also a valid LCS of the same length.");
        System.out.println("Tie-breaking in backtracking determines which one you get.");
    }
}

public class LCSSpaceOptimized {

    /**
     * Computes LCS length using only O(min(m, n)) space.
     *
     * Key trick: ensure the shorter string drives the column dimension
     * so we allocate the smallest possible 1D arrays.
     *
     * Time:  O(m * n)
     * Space: O(min(m, n))  — only two rows in memory at once
     */
    public static int lcsLengthOptimized(String text1, String text2) {
        // Always make text2 the shorter string to minimize array size
        if (text1.length() < text2.length()) {
            String temp = text1;
            text1 = text2;
            text2 = temp;
        }

        int cols = text2.length();

        // previousRow represents dp[i-1][0..cols]
        // currentRow  represents dp[i][0..cols]
        int[] previousRow = new int[cols + 1]; // implicitly all zeros = base case
        int[] currentRow  = new int[cols + 1];

        for (int i = 1; i <= text1.length(); i++) {
            // Reset currentRow for this iteration
            // (col 0 stays 0 — empty prefix base case)
            for (int j = 1; j <= cols; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    // Match: take the diagonal value from previousRow
                    currentRow[j] = previousRow[j - 1] + 1;
                } else {
                    // No match: best of skipping from either direction
                    currentRow[j] = Math.max(previousRow[j], currentRow[j - 1]);
                }
            }

            // Roll: current becomes previous for the next iteration.
            // Swap references instead of copying — O(1) operation.
            int[] swap = previousRow;
            previousRow = currentRow;
            currentRow  = swap; // reuse the old previousRow array memory
        }

        // After all rows, previousRow holds the final row's values
        return previousRow[cols];
    }

    public static void main(String[] args) {
        // Test with the classic example
        System.out.println("LCS('ABCBDAB', 'BDCAB') = "
            + lcsLengthOptimized("ABCBDAB", "BDCAB"));

        // Edge cases
        System.out.println("LCS('', 'ABC')     = "
            + lcsLengthOptimized("", "ABC"));

        System.out.println("LCS('ABC', 'ABC')  = "
            + lcsLengthOptimized("ABC", "ABC"));

        System.out.println("LCS('ABC', 'XYZ')  = "
            + lcsLengthOptimized("ABC", "XYZ"));

        // Large-ish input to show the approach stays snappy
        String longText1 = "AGGTAB".repeat(500);  // 3000 chars
        String longText2 = "GXTXAYB".repeat(400); // 2800 chars
        long start = System.currentTimeMillis();
        int result  = lcsLengthOptimized(longText1, longText2);
        long elapsed = System.currentTimeMillis() - start;
        System.out.println("LCS(3000-char, 2800-char) = " + result
            + "  [computed in " + elapsed + "ms]");
    }
}

/**
 * Demonstrates three practical derivations from LCS:
 *   1. Minimum insertions + deletions to convert text1 -> text2
 *   2. Shortest Common Supersequence length
 *   3. Normalized similarity score (useful for plagiarism detection)
 */
public class LCSApplications {

    /** Computes LCS length using the space-optimized two-row approach. */
    private static int lcsLength(String text1, String text2) {
        int rows = text1.length();
        int cols = text2.length();
        int[] previousRow = new int[cols + 1];
        int[] currentRow  = new int[cols + 1];

        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    currentRow[j] = previousRow[j - 1] + 1;
                } else {
                    currentRow[j] = Math.max(previousRow[j], currentRow[j - 1]);
                }
            }
            int[] swap = previousRow;
            previousRow = currentRow;
            currentRow  = swap;
        }
        return previousRow[cols];
    }

    /**
     * Min number of character-level insertions + deletions to transform
     * source into target. (No substitutions — pure insert/delete model)
     */
    public static int minInsertionsAndDeletions(String source, String target) {
        int lcs = lcsLength(source, target);
        // Characters in source NOT in LCS must be deleted
        int deletions   = source.length() - lcs;
        // Characters in target NOT in LCS must be inserted
        int insertions  = target.length() - lcs;
        return deletions + insertions;
    }

    /**
     * Length of the Shortest Common Supersequence.
     * SCS contains both strings as subsequences with minimum total length.
     */
    public static int shortestCommonSupersequenceLength(String text1, String text2) {
        int lcs = lcsLength(text1, text2);
        // Each LCS character is shared — count it once, not twice
        return text1.length() + text2.length() - lcs;
    }

    /**
     * Returns a similarity ratio in [0.0, 1.0].
     * 1.0 means identical, 0.0 means nothing in common.
     * Formula: 2 * LCS / (|text1| + |text2|)  — Sørensen–Dice style
     */
    public static double similarityScore(String text1, String text2) {
        if (text1.isEmpty() && text2.isEmpty()) return 1.0;
        if (text1.isEmpty() || text2.isEmpty()) return 0.0;
        int lcs = lcsLength(text1, text2);
        return (2.0 * lcs) / (text1.length() + text2.length());
    }

    public static void main(String[] args) {
        String original = "SUNDAY";
        String revised  = "SATURDAY";

        System.out.println("Source  : " + original);
        System.out.println("Target  : " + revised);
        System.out.println();

        System.out.println("Min edits (insert+delete) : "
            + minInsertionsAndDeletions(original, revised));

        System.out.println("Shortest Common Superseq  : length "
            + shortestCommonSupersequenceLength(original, revised));

        System.out.printf("Similarity score           : %.2f (%.0f%% similar)%n",
            similarityScore(original, revised),
            similarityScore(original, revised) * 100);

        System.out.println();
        // Demonstrate identical strings
        System.out.printf("Similarity('ABC', 'ABC')   : %.2f%n",
            similarityScore("ABC", "ABC"));
        // Demonstrate completely different strings
        System.out.printf("Similarity('ABC', 'XYZ')   : %.2f%n",
            similarityScore("ABC", "XYZ"));
    }
}