Definition
- Longest Common Subsequence (LCS) – finds the longest sequence of characters that appear in both strings in the same relative order, but not necessarily contiguously.
- 2D DP table –
dp[i][j]stores the LCS length of the firsticharacters of A and the firstjcharacters of B. - Match rule – if
A[i-1] == B[j-1], thendp[i][j] = dp[i-1][j-1] + 1, meaning both characters join the subsequence. - Mismatch rule – if characters differ,
dp[i][j] = max(dp[i-1][j], dp[i][j-1]), inheriting the better result from dropping one character. - Complexity – O(m * n) time and space, reducible to O(min(m, n)) space with a rolling row.
Two branches of the National Bank of India each keep a transaction-code log. The compliance team wants the longest shared ordered pattern between the two logs. When the current codes match, the shared pattern grows by one; when they differ, the team keeps whichever side's extension gave the longer shared pattern so far.
Understanding the Concepts
What is the Longest Common Subsequence?
A subsequence is a sequence of characters taken from a string in their original order, but not necessarily contiguously. The Longest Common Subsequence (LCS) of two strings is the longest such sequence that appears in both. For example, for strings ABCDE and ACE, the LCS is ACE with length 3.
package com.bank.core;
// String A: "TRANSFER"
// String B: "TRANSFORM"
// LCS: "TRANSF" with some variations
// Characters appear in both in the same order, not necessarily adjacent
Why is LCS important?
LCS is the foundation for many string comparison problems. Unix diff tools use LCS to find what is common between two file versions. Edit distance (Levenshtein distance) is closely related: the minimum edits equal m + n - 2 * LCS. The shortest common supersequence length equals m + n - LCS. Understanding LCS unlocks this entire family of two-string dynamic programs.
package com.bank.core;
// Relationships:
// Edit distance (insertions + deletions only) = m + n - 2 * LCS
// Shortest common supersequence length = m + n - LCS
// Diff tool output = characters NOT in the LCS
How does the 2D DP table work?
You build a table of size (m+1) x (n+1) where m and n are the lengths of the two strings. The zero-th row and zero-th column are all zeros, representing the LCS of any prefix with an empty string. You fill the table row by row. When the characters at position i in A and position j in B match, both characters extend the subsequence, so you take the diagonal value plus one. When they differ, you cannot extend, so you take the better of dropping the last character of A or B.
package com.bank.service;
public class LCSCalculator {
public int longestCommonSubsequence(String a, String b) {
int m = a.length();
int n = b.length();
int[][] dp = new int[m + 1][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)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
public static void main(String[] args) {
LCSCalculator calc = new LCSCalculator();
System.out.println(calc.longestCommonSubsequence("ABCDE", "ACE"));
System.out.println(calc.longestCommonSubsequence("TRANSFER", "TRANSFORM"));
}
}
3
7
How do you reconstruct the actual subsequence?
To find the actual LCS string, not just the length, you backtrack from dp[m][n]. When the characters at position i and j match, include that character and move diagonally to dp[i-1][j-1]. When they differ, move toward the larger of dp[i-1][j] or dp[i][j-1]. Collect characters in reverse and then reverse the result.
package com.bank.service;
public class LCSReconstructor {
public String findLCS(String a, String b) {
int m = a.length();
int n = b.length();
int[][] dp = new int[m + 1][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)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
// Backtrack to find the actual subsequence
StringBuilder sb = new StringBuilder();
int i = m, j = n;
while (i > 0 && j > 0) {
if (a.charAt(i - 1) == b.charAt(j - 1)) {
sb.append(a.charAt(i - 1));
i--;
j--;
} else if (dp[i - 1][j] > dp[i][j - 1]) {
i--;
} else {
j--;
}
}
return sb.reverse().toString();
}
public static void main(String[] args) {
LCSReconstructor recon = new LCSReconstructor();
System.out.println(recon.findLCS("ABCDE", "ACE"));
}
}
ACE
How do you optimize space with a rolling row?
Because each row of the DP table only depends on the previous row, you can use two 1D arrays instead of a full 2D table. This reduces space from O(m * n) to O(min(m, n)) by making the shorter string the column dimension.
package com.bank.service;
public class LCSSpaceOptimized {
public int longestCommonSubsequence(String a, String b) {
if (a.length() < b.length()) {
String temp = a; a = b; b = temp; // ensure b is shorter
}
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[] temp = prev;
prev = curr;
curr = temp;
java.util.Arrays.fill(curr, 0);
}
return prev[n];
}
}
How is LCS different from Longest Common Substring?
LCS allows gaps between matched characters (non-contiguous), while Longest Common Substring requires the match to be contiguous. The table structure looks similar but the mismatch rule differs: LCS inherits from neighbors, while Longest Common Substring resets to zero.
| Aspect | Longest Common Subsequence | Longest Common Substring |
|---|---|---|
| Contiguity | Characters need not be adjacent | Characters must be adjacent |
| Mismatch rule | max(dp[i-1][j], dp[i][j-1]) | 0 (reset) |
| Answer location | Bottom-right corner dp[m][n] | Global maximum over all cells |
| Example: ABCDE, ABFCE | LCS = ABCE (length 4) | Substring = AB (length 2) |
package com.bank.core;
// LCS of "TRANSFER" and "TRANSFORM": non-contiguous match allowed
// Longest Common Substring: must be contiguous block
// Different recurrence on mismatch is the key distinction
What about a banking use case?
At the National Bank of India, compliance compares two accounts' ordered transaction-code logs to find the longest shared ordered pattern that might indicate coordinated activity. Because shared codes do not have to be adjacent, only in the same order, the LCS captures patterns that a contiguous match would miss.
package com.bank.service;
public class TransactionPatternMatcher {
private final LCSCalculator lcsCalculator = new LCSCalculator();
public int findSharedPatternLength(String log1, String log2) {
return lcsCalculator.longestCommonSubsequence(log1, log2);
}
public static void main(String[] args) {
TransactionPatternMatcher matcher = new TransactionPatternMatcher();
String account1Log = "DWSCWTD"; // D=deposit, W=withdraw, S=salary, C=cheque, T=transfer
String account2Log = "DSCWTWD";
int shared = matcher.findSharedPatternLength(account1Log, account2Log);
System.out.println("Shared pattern length: " + shared);
}
}
Shared pattern length: 6
What are common mistakes?
The most common mistake is confusing subsequence with substring and using the wrong mismatch rule. Another mistake is indexing: the DP table uses 1-based indexing for the strings but charAt is 0-based, so you must use charAt(i-1) not charAt(i). A third mistake is forgetting the zero border, which serves as the base case for empty prefixes.
package com.bank.core;
// WRONG: using charAt(i) instead of charAt(i-1)
// dp[i][j] represents prefix of length i, but charAt is 0-based
// if (a.charAt(i) == b.charAt(j)) // OFF BY ONE!
// CORRECT: adjust for 0-based charAt
// if (a.charAt(i - 1) == b.charAt(j - 1))
What should a senior engineer know?
A senior engineer should know that LCS is the backbone of diff algorithms used in version control systems like Git. The Hunt-Szymanski algorithm improves average-case LCS performance when the alphabet is large and matches are sparse. For very long strings, the space-optimized rolling-row version is essential, though it sacrifices the ability to reconstruct the actual subsequence without additional work.
package com.bank.core;
// Senior notes:
// 1. LCS powers Unix diff and Git diff
// 2. Space optimization: O(min(m,n)) with rolling row
// 3. Reconstruction requires full table or Hirschberg's algorithm
// 4. Edit distance = m + n - 2 * LCS (for insert/delete only)
// 5. Time: O(m*n), no known sub-quadratic worst-case algorithm
Visual Overview
LCS table for A = "ACE" and B = "ABCDE":
"" A B C D E
"" [ 0 0 0 0 0 0 ]
A [ 0 1 1 1 1 1 ]
C [ 0 1 1 2 2 2 ]
E [ 0 1 1 2 2 3 ]
^
answer = 3
Fill rules:
┌─────────────────────────────────────────┐
│ If A[i-1] == B[j-1]: │
│ dp[i][j] = dp[i-1][j-1] + 1 │
│ (diagonal + 1) │
│ │
│ If A[i-1] != B[j-1]: │
│ dp[i][j] = max(dp[i-1][j], │
│ dp[i][j-1]) │
│ (max of top, left) │
└─────────────────────────────────────────┘
Backtracking to reconstruct "ACE":
Start at dp[3][5] = 3
┌────────────────────────────────────────┐
│ E == E -> include 'E', move diagonal │
│ C != D -> move to max(dp[1][3], │
│ dp[2][4]) -> go left │
│ C == C -> include 'C', move diagonal │
│ A != B -> move to max(dp[0][0], │
│ dp[1][1]) -> go up │
│ A == A -> include 'A', move diagonal │
│ Reverse: E,C,A -> "ACE" │
└────────────────────────────────────────┘
Key Takeaway
Longest Common Subsequence is the foundational two-dimensional dynamic programming problem for comparing strings. You define dp[i][j] as the length of the longest common subsequence of the first i characters of string A and the first j characters of string B. The table starts with a zero border for empty prefixes and fills row by row using two simple rules: when the current characters match, add one to the diagonal; when they differ, take the maximum of the top and left cells.
The answer sits at dp[m][n], and reconstructing the actual subsequence requires backtracking through the table from that corner. On a match you include the character and move diagonally; on a mismatch you move toward the larger neighbor. The time and space complexity are both O(m * n), and space reduces to O(min(m, n)) with a rolling row that keeps only the previous row.
The distinction between LCS and Longest Common Substring is a frequent interview trap. LCS allows gaps between matched characters and inherits from neighbors on a mismatch, while Longest Common Substring requires contiguity and resets to zero. LCS also has deep practical applications: it powers diff tools, connects to edit distance through the formula edits = m + n - 2 * LCS, and determines the shortest common supersequence length as m + n - LCS.
At the National Bank of India, compliance compared two accounts' ordered transaction-code logs to find the longest shared ordered pattern. Because shared codes do not have to be adjacent, only in the same relative order, the LCS captured coordination patterns that a contiguous-match test would miss. The rolling-row optimization kept memory manageable for very long transaction histories.
Remember one sentence: when characters match take the diagonal plus one, when they differ take the max of top and left, and the answer is in the bottom-right corner.
---