AOAD, Snippets

Java Program for Longest Common Subsequence (LCS) Problem

Leave a comment

The Longest Common Subsequence (LCS) problem asks for the longest sequence of characters that appears in the same relative order in two strings, but not necessarily contiguously. For example, the LCS of "president" and "providence" is "priden" (length 6). LCS is solved efficiently using dynamic programming in O(m×n) time, where m and n are the lengths of the two sequences. It is widely used in diff tools, DNA sequence analysis, and file comparison utilities.

Longest Common Subsequence (LCS) Implementation in Java

import java.io.*;

class LongestCommonSubsequence {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        System.out.print("Enter length of Sequence 1: ");
        int len1 = Integer.parseInt(reader.readLine());

        System.out.println("Enter Sequence 1:");
        String seq1 = reader.readLine();

        System.out.print("Enter length of Sequence 2: ");
        int len2 = Integer.parseInt(reader.readLine());

        System.out.print("Enter Sequence 2: ");
        String seq2 = reader.readLine();

        // dpTable[i][j] = length of LCS of seq1[0..i-1] and seq2[0..j-1]
        int[][] dpTable      = new int[50][50];
        // directionTable[i][j] records how we got to dpTable[i][j]:
        //   '' means seq1[i] == seq2[j] (diagonal -- character is in LCS)
        //   '|' means we took dpTable[i-1][j]  (from above)
        //   '-' means we took dpTable[i][j-1]  (from left)
        char[][] directionTable = new char[len1 + 1][len2 + 1];

        // Base cases: LCS of empty prefix is 0
        for (int i = 0; i <= len1; i++) dpTable[i][0] = 0;
        for (int j = 0; j <= len2; j++) dpTable[0][j] = 0;

        System.out.println("\nDP Table:");

        // Fill the DP table row by row
        for (int i = 0; i < len1; i++) {
            for (int j = 0; j < len2; j++) {
                if (i == 0 || j == 0) {
                    // Print border cells (value 0) without computing LCS
                    System.out.print(dpTable[i][j]);
                    continue;
                }

                if (seq1.charAt(i) == seq2.charAt(j)) {
                    // Characters match: extend the LCS by 1
                    directionTable[i][j] = '';
                    dpTable[i][j]        = dpTable[i - 1][j - 1] + 1;
                    System.out.print(directionTable[i][j] + dpTable[i][j]);
                } else if (dpTable[i - 1][j] >= dpTable[i][j - 1]) {
                    // LCS from above is at least as long
                    directionTable[i][j] = '|';
                    dpTable[i][j]        = dpTable[i - 1][j];
                    System.out.print(directionTable[i][j] + dpTable[i][j]);
                } else {
                    // LCS from the left is longer
                    directionTable[i][j] = '-';
                    dpTable[i][j]        = dpTable[i][j - 1];
                    System.out.print(directionTable[i][j] + dpTable[i][j]);
                }
            }
            System.out.println();
        }

        // Traceback: follow '' arrows to collect LCS character indices
        int   row         = len1 - 1;
        int   col         = len2 - 1;
        int[] lcsIndices  = new int[10];   // stores row indices of matched characters
        int   lcsLength   = 1;             // 1-indexed counter

        System.out.print("\nLongest Common Subsequence: ");

        while (row > 0 || col > 0) {
            if (directionTable[row][col] == '') {
                // Diagonal arrow: this position is part of the LCS
                lcsIndices[lcsLength] = row;
                lcsLength++;
                row--;
                col--;
            } else if (directionTable[row][col] == '|') {
                // Arrow from above: move up
                row--;
            } else {
                // Arrow from left: move left
                col--;
            }
        }

        // Print LCS characters in forward order (lcsIndices was filled in reverse)
        for (int i = lcsLength - 1; i > 0; i--) {
            System.out.print(seq1.charAt(lcsIndices[i]));
        }
        System.out.println();
    }
}

How the Code Works

  1. DP table: dpTable[i][j] stores the length of the LCS of seq1[0..i-1] and seq2[0..j-1]. All row-0 and column-0 entries are 0 (base case: LCS with empty string is 0).
  2. Recurrence:
    • If seq1[i] == seq2[j]: the characters match → dpTable[i][j] = dpTable[i-1][j-1] + 1, and a diagonal arrow '\' is recorded.
    • If dpTable[i-1][j] >= dpTable[i][j-1]: inherit from above → dpTable[i][j] = dpTable[i-1][j], record '|'.
    • Otherwise: inherit from left → dpTable[i][j] = dpTable[i][j-1], record '-'.
  3. Direction table: directionTable[i][j] encodes the decision made at each cell, enabling traceback.
  4. Traceback: starting at dpTable[len1-1][len2-1], following '\' arrows (diagonal matches) collects the LCS character indices in reverse. Non-diagonal arrows just move the pointer without collecting characters.
  5. Print: the collected indices are printed in reverse order to produce the LCS in left-to-right sequence.

Sample Output

Enter length of Sequence 1: 9
Enter Sequence 1: president
Enter length of Sequence 2: 10
Enter Sequence 2: providence

DP Table:
(table rows showing dpTable values and direction arrows)

Longest Common Subsequence: priden

Output Explanation

  1. The two input strings are "president" (length 9) and "providence" (length 10).
  2. The DP table is filled by comparing characters at each (row, column) position. Cells with matching characters get a diagonal '\' arrow and the LCS count increments.
  3. The traceback follows diagonal arrows from the bottom-right corner back to the top-left, collecting matched characters: p, r, i, d, e, n.
  4. The LCS is "priden" with length 6. These characters appear in both strings in the same relative left-to-right order, though not necessarily consecutively.

See Also

Conclusion

The LCS algorithm is a foundational dynamic programming problem that teaches the essential pattern: define a subproblem, fill a table bottom-up, then traceback to reconstruct the solution. It is directly related to the edit-distance (Levenshtein) problem and underpins tools like Unix diff. Extending this to more than two sequences or applying it to DNA alignment are natural next steps once the two-sequence version is well understood.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.