Longest Common Subsequence LCS Java | Fresher Interview

Direct Answer

LCS finds the longest sequence appearing in both strings in order but not necessarily contiguous. Use a 2D table where dp[i][j] = LCS length of the first i chars of A and first j of B. If A[i-1] == B[j-1], dp[i][j] = dp[i-1][j-1] + 1; else max(dp[i-1][j], dp[i][j-1]). O(m*n) time and space.

Deep Dive & Architecture

A subsequence keeps relative order but may skip characters, so it is different from a substring. The DP table answers smaller prefix questions: dp[i][j] stores the LCS length for the first i characters of the first string and the first j characters of the second.

An empty prefix has an LCS length of zero, which fills row 0 and column 0. When the current characters match, they can extend a smaller common subsequence, so use the diagonal cell plus one. When they differ, skip one current character and keep the better result from the cell above or the cell to the left.

Worked example: ABC and AC

A matches A, so that cell becomes 1. B does not match C, so the best neighboring value stays 1. Finally C matches C, so the diagonal value 1 becomes 2. The LCS is AC, with length 2.

The full table uses O(m × n) time and space. If only the length is needed, two rows are enough for O(min(m, n)) space. If the actual sequence is needed, walk backward from dp[m][n]: take matching characters, otherwise move toward the larger neighboring cell.

Code Example

int lcs(String a, String b) {
    int m = a.length(), n = b.length();
    int[][] dp = new int[m + 1][n + 1];   // dp[0][*]=dp[*][0]=0 (base)
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++) {
            if (a.charAt(i-1) == b.charAt(j-1))
                dp[i][j] = dp[i-1][j-1] + 1;          // match: diagonal +1
            else
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]); // no match
        }
    return dp[m][n];
}

// a="AGGTAB", b="GXTXAYB" -> LCS "GTAB" length 4

Common Mistakes & Pitfalls

• Subsequence vs substring: LCS allows gaps; substring must be contiguous (different DP).
• Off-by-one: with 1-indexed dp, compare a.charAt(i-1) and b.charAt(j-1).
• Forgetting base row/column: dp[0][*] and dp[*][0] are 0.
• Wrong no-match transition: it's max of the two neighbors, not the diagonal.