Definition
- Longest Common Subsequence (LCS) – the longest sequence of elements appearing in both inputs in order, not contiguously.
- Match rule – if
A[i-1] == B[j-1], thendp[i][j] = dp[i-1][j-1] + 1(extend the match). - Mismatch rule –
dp[i][j] = max(dp[i-1][j], dp[i][j-1])(drop one element from either side). - Base – first row and column are zero (empty prefix).
- Space – O(m * n) full table, O(min(m, n)) with two rolling rows.
- Reconstruction – walk backward from dp[m][n] using stored directions.
The National Bank of India compares two versions of an account's transaction log, one from the core system and one from a reconciliation feed. The LCS reveals the longest ordered set of matching transactions, highlighting what was inserted or removed between versions.
Understanding the Concepts
What is the Longest Common Subsequence?
The Longest Common Subsequence (LCS) of two sequences is the longest sequence of elements that appears in both inputs in the same relative order, without requiring the elements to be contiguous. For strings "ABCBDAB" and "BDCAB", one LCS is "BCAB" with length 4.
LCS is the foundation of diff tools (showing what changed between file versions), DNA sequence alignment, and version comparison.
package com.bank.dsa;
public class LcsBasic {
public static int lcs(String a, String b) {
int m = a.length(), 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; // match: extend diagonal
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); // drop one side
}
}
}
return dp[m][n];
}
public static void main(String[] args) {
System.out.println("LCS length: " + lcs("ABCBDAB", "BDCAB"));
}
}
LCS length: 4
How does the DP grid work?
The grid has (m + 1) rows and (n + 1) columns. Cell dp[i][j] stores the LCS length of the first i characters of A and the first j characters of B. The first row and first column are all zeros because the LCS of any string with an empty string is zero.
When A[i-1] equals B[j-1], the current characters match, so we extend the best LCS up to the previous characters: dp[i][j] = dp[i-1][j-1] + 1. When they differ, we cannot use both current characters, so we take the better of dropping the last character from A (dp[i-1][j]) or dropping the last from B (dp[i][j-1]).
How do you reconstruct the actual LCS?
Walk backward from dp[m][n]. If A[i-1] == B[j-1], include this character and move diagonally. Otherwise, move in the direction of the larger neighbour (up or left).
package com.bank.dsa;
public class LcsReconstruct {
public static String findLCS(String a, String b) {
int m = a.length(), 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++)
dp[i][j] = a.charAt(i - 1) == b.charAt(j - 1)
? dp[i - 1][j - 1] + 1
: Math.max(dp[i - 1][j], dp[i][j - 1]);
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) {
System.out.println("LCS: " + findLCS("ABCBDAB", "BDCAB"));
}
}
LCS: BCAB
How do you optimise space with rolling rows?
Each row depends only on the previous row, so keep two arrays and alternate. This reduces space from O(m * n) to O(min(m, n)). However, reconstruction is lost because we no longer have the full grid.
package com.bank.dsa;
public class LcsRolling {
public static int lcs(String a, String b) {
if (a.length() < b.length()) return lcs(b, a); // shorter string as columns
int n = b.length();
int[] prev = new int[n + 1];
int[] curr = new int[n + 1];
for (int i = 1; i <= a.length(); 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];
}
public static void main(String[] args) {
System.out.println("LCS length: " + lcs("ABCBDAB", "BDCAB"));
}
}
LCS length: 4
How is LCS different from Longest Common Substring?
| Aspect | LCS (Subsequence) | Longest Common Substring |
|---|---|---|
| Contiguity | Not required | Must be contiguous |
| Match rule | dp[i-1][j-1] + 1 | dp[i-1][j-1] + 1 |
| Mismatch rule | max(dp[i-1][j], dp[i][j-1]) | 0 (reset) |
| Answer location | dp[m][n] | max value in entire table |
| Time | O(m * n) | O(m * n) |
package com.bank.dsa;
public class LongestCommonSubstring {
public static int longestSubstring(String a, String b) {
int m = a.length(), n = b.length(), best = 0;
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;
best = Math.max(best, dp[i][j]);
}
// else dp[i][j] remains 0
}
return best;
}
public static void main(String[] args) {
System.out.println("Longest common substring: " + longestSubstring("ABCBDAB", "BDCAB"));
}
}
Longest common substring: 2
What are common mistakes?
The most common mistake is confusing LCS (subsequence, non-contiguous) with longest common substring (contiguous). The mismatch handling is completely different: LCS takes the max of two neighbours, while substring resets to zero.
Another mistake is indexing: dp[i][j] compares A[i-1] with B[j-1], not A[i] with B[j]. Off-by-one errors cause wrong results or ArrayIndexOutOfBoundsException.
What are the edge cases?
When one string is empty, the LCS length is zero. When both strings are identical, the LCS is the string itself. When the strings share no characters, the LCS is zero.
package com.bank.dsa;
public class LcsEdge {
public static void main(String[] args) {
System.out.println(LcsBasic.lcs("", "ABC")); // 0
System.out.println(LcsBasic.lcs("ABC", "ABC")); // 3
System.out.println(LcsBasic.lcs("ABC", "XYZ")); // 0
}
}
0
3
0
When should you use LCS in banking?
At the National Bank of India, the reconciliation team compares transaction logs from the core banking system and the payment gateway. The LCS reveals the longest ordered set of matching transactions, highlighting what was inserted or deleted between the two feeds.
package com.bank.service;
public class TransactionReconciler {
public static int matchingTransactions(String[] coreLog, String[] gatewayLog) {
int m = coreLog.length, n = gatewayLog.length;
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
dp[i][j] = coreLog[i - 1].equals(gatewayLog[j - 1])
? dp[i - 1][j - 1] + 1
: Math.max(dp[i - 1][j], dp[i][j - 1]);
return dp[m][n];
}
public static void main(String[] args) {
String[] core = {"TXN001", "TXN002", "TXN003", "TXN005"};
String[] gateway = {"TXN001", "TXN003", "TXN004", "TXN005"};
System.out.println("Matching transactions: " + matchingTransactions(core, gateway));
}
}
Matching transactions: 3
What should a senior engineer know?
A senior engineer should know that LCS connects to edit distance: when only insert and delete are allowed (no replace), the edit distance is m + n - 2 * LCS(A, B). This relationship helps verify solutions.
For very long sequences, Hirschberg's algorithm computes the LCS in O(m * n) time with only O(min(m, n)) space while still reconstructing the actual subsequence, using a divide-and-conquer approach on the rolling rows.
The Hunt-Szymanski algorithm is faster than O(m * n) when the number of matching character pairs is small, which is common in diff tools where most lines match.
Visual Overview
LCS Grid: "ABCB" vs "BDCB"
───────────────────────────
_ B D C B
_ 0 0 0 0 0
A 0 0 0 0 0
B 0 [1] 1 1 1
C 0 1 1 [2] 2
B 0 1 1 2 [3] ← answer
[x] = match: dp[i-1][j-1] + 1
Others = max(above, left)
Reconstruction: walk from dp[4][4]=3
B(4,4)←match C(3,3)←match B(2,1)←match
LCS = "BCB"
Key Takeaway
The Longest Common Subsequence finds the longest ordered set of elements appearing in both inputs without requiring contiguity. The DP grid has two simple rules: when the current characters match, add one to the diagonal cell; when they differ, take the larger of the cell above and the cell to the left. The answer is in the bottom-right corner.
The space optimisation keeps two rolling rows since each row depends only on the previous one. This reduces memory from O(m * n) to O(min(m, n)), but reconstruction of the actual LCS requires the full grid or Hirschberg's divide-and-conquer approach.
At the National Bank of India, the reconciliation team used LCS to compare transaction logs from the core system and the payment gateway, extracting the longest ordered set of matching entries and highlighting what was inserted or deleted. The rolling-row version handled long logs efficiently.
The senior-level connection is that edit distance with insert and delete only equals m + n - 2 * LCS. For diff tools, the Hunt-Szymanski algorithm is faster when most lines match.
Remember one sentence: on a match extend the diagonal by one, on a mismatch take the better of the two neighbours, and the answer sits in the bottom-right corner.
---