LCS Tie-Breaking Bug Broke Code Review Tool's Diff

public class NaiveLCSRecursion {

    /**
     * Computes LCS length using pure recursion (no memoization).
     * Intentionally simple to show the exponential cost.
     * Time complexity: O(2^(m+n)) worst case.
     */
    public static int lcsLength(String text1, String text2, int i, int j) {
        // Base case: empty string
        if (i == 0 || j == 0) {
            return 0;
        }

        if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
            // Last characters match: include them
            return 1 + lcsLength(text1, text2, i - 1, j - 1);
        } else {
            // No match: try skipping from each string
            return Math.max(
                lcsLength(text1, text2, i - 1, j),
                lcsLength(text1, text2, i, j - 1)
            );
        }
    }

    public static void main(String[] args) {
        String text1 = "ABCBDAB";
        String text2 = "BDCAB";
        long start = System.nanoTime();
        int result = lcsLength(text1, text2, text1.length(), text2.length());
        long end = System.nanoTime();
        System.out.println("LCS length: " + result);
        System.out.println("Time: " + (end - start) / 1_000_000 + " ms");
        // For such a small input it's fast, but try with length 15+ and it becomes unusable.
    }
}

public class LCSMemoization {

    private static int[][] memo;

    /**
     * Top-down DP with memoization for LCS length.
     * Returns the LCS length using a cached 2D table.
     */
    public static int lcsLength(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        // Initialize memo with -1 (sentinel for uncomputed)
        memo = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                memo[i][j] = -1;
            }
        }
        return lcsHelper(text1, text2, m, n);
    }

    private static int lcsHelper(String text1, String text2, int i, int j) {
        // Base case
        if (i == 0 || j == 0) {
            return 0;
        }
        // Return cached result if available
        if (memo[i][j] != -1) {
            return memo[i][j];
        }

        int result;
        if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
            result = 1 + lcsHelper(text1, text2, i - 1, j - 1);
        } else {
            result = Math.max(
                lcsHelper(text1, text2, i - 1, j),
                lcsHelper(text1, text2, i, j - 1)
            );
        }
        // Cache before returning
        memo[i][j] = result;
        return result;
    }

    public static void main(String[] args) {
        String text1 = "ABCBDAB";
        String text2 = "BDCAB";
        long start = System.nanoTime();
        int result = lcsLength(text1, text2);
        long end = System.nanoTime();
        System.out.println("LCS length: " + result);
        System.out.println("Time: " + (end - start) / 1_000_000 + " ms");

        // Larger test
        String big1 = "AGGTAB".repeat(500);
        String big2 = "GXTXAYB".repeat(400);
        start = System.nanoTime();
        result = lcsLength(big1, big2);
        end = System.nanoTime();
        System.out.println("LCS length (3000 vs 2800): " + result);
        System.out.println("Time: " + (end - start) / 1_000_000 + " ms");
        // Note: this will likely throw StackOverflowError for 3000 length due to deep recursion
        // demonstrating the risk of memoization for large inputs.
    }
}

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"));
    }
}

import java.util.*;

/**
 * Block-based LCS that splits long strings into segments to improve
 * cache performance and allow parallel processing.
 * This is a simplified demonstration of the concept.
 */
public class LCSBlockOptimized {

    /**
     * Splits each string into blocks of given size, computes LCS on
     * aligned blocks, and combines results. Not exact but useful for
     * approximate matching in production.
     */
    public static int approximateLCS(String text1, String text2, int blockSize) {
        int m = text1.length();
        int n = text2.length();
        int totalLCS = 0;
        
        // Simple sliding window block comparison
        for (int i = 0; i < m; i += blockSize) {
            int end1 = Math.min(i + blockSize, m);
            String block1 = text1.substring(i, end1);
            
            for (int j = 0; j < n; j += blockSize) {
                int end2 = Math.min(j + blockSize, n);
                String block2 = text2.substring(j, end2);
                
                // Compute exact LCS for small blocks
                totalLCS += exactLCS(block1, block2);
            }
        }
        return totalLCS;
    }

    private static int exactLCS(String a, String b) {
        int m = a.length();
        int n = b.length();
        int[] prev = new int[n + 1];
        int[] curr = new int[n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (a.charAt(i - 1) == b.charAt(j - 1)) {
                    curr[j] = prev[j - 1] + 1;
                } else {
                    curr[j] = Math.max(prev[j], curr[j - 1]);
                }
            }
            int[] tmp = prev; prev = curr; curr = tmp;
        }
        return prev[n];
    }

    public static void main(String[] args) {
        String s1 = "GCGCCATGCGTAGCTAGCTAGC";
        String s2 = "GCCATGCGTAGCGCTAGCTAGC";
        long start = System.nanoTime();
        int approx = approximateLCS(s1, s2, 8);
        long end = System.nanoTime();
        System.out.println("Approximate LCS (blockSize=8): " + approx);
        System.out.println("Time: " + (end - start) / 1_000_000 + " ms");
        // Compare with exact
        int[] prev = new int[s2.length()+1];
        int[] curr = new int[s2.length()+1];
        for (int i=1; i<=s1.length(); i++) {
            for (int j=1; j<=s2.length(); j++) {
                if (s1.charAt(i-1) == s2.charAt(j-1)) curr[j]=prev[j-1]+1;
                else curr[j]=Math.max(prev[j],curr[j-1]);
            }
            int[] t=prev; prev=curr; curr=t;
        }
        System.out.println("Exact LCS: " + prev[s2.length()]);
    }
}