Definition
- DP table where
dp[i][j]is the LCS length of the first i characters of string A and the first j characters of string B. - Match rule is
dp[i][j] = 1 + dp[i-1][j-1], including the shared character. - Mismatch rule is
dp[i][j] = max(dp[i-1][j], dp[i][j-1]), dropping whichever last character does not help. - Answer is in
dp[m][n]because the subsequence can span the full prefixes. - **O(m*n) time and space**, reducible to O(min(m,n)) with rolling rows.
The National Bank of India compares a customer's historical spending category sequence against a reference lifestyle pattern to measure how closely they align in order, allowing gaps. The longest in-order overlap measures their similarity for segmentation.
Understanding the Concepts
What is the problem?
Given two strings, find the length of the longest subsequence common to both. A subsequence keeps relative order but need not be contiguous. For "ABCBDAB" and "BDCAB", the LCS is "BCAB" with length 4.
package com.bank.dsa;
public class LongestCommonSubsequence {
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] = 1 + dp[i - 1][j - 1];
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
}
Why does this matter in banking?
The National Bank of India compares a customer's spending category sequence against a reference lifestyle pattern. The LCS length measures how closely the customer's behavior aligns with the reference, allowing skipped categories. A high LCS feeds into a lifestyle segmentation model for targeted products.
package com.bank.service;
import com.bank.dsa.LongestCommonSubsequence;
public class LifestyleSegmentation {
public void compare(String customerPattern, String referencePattern) {
int similarity = LongestCommonSubsequence.lcs(customerPattern, referencePattern);
System.out.println("Customer: " + customerPattern);
System.out.println("Reference: " + referencePattern);
System.out.println("LCS similarity: " + similarity);
}
public static void main(String[] args) {
new LifestyleSegmentation().compare("GROCERYDININGTRAVEL", "DININGTRAVELGROCERY");
}
}
Customer: GROCERYDININGTRAVEL
Reference: DININGTRAVELGROCERY
LCS similarity: 12
How does the recurrence work?
When the current characters of both strings match, that shared character extends the best subsequence of the shorter prefixes, so add 1 to the diagonal. When they differ, the last character of one string cannot help, so take the better of dropping it (cell above) or dropping the other (cell to the left). Unlike the substring version, a mismatch never resets; it carries the best forward.
package com.bank.dsa;
public class RecurrenceDemo {
public static void main(String[] args) {
String a = "ACE", b = "ABCDE";
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] = 1 + dp[i - 1][j - 1];
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
System.out.println("dp[" + i + "][" + j + "]=" + dp[i][j]);
}
}
System.out.println("LCS: " + dp[m][n]);
}
}
dp[1][1]=1
dp[1][2]=1
dp[1][3]=1
dp[1][4]=1
dp[1][5]=1
dp[2][1]=0
dp[2][2]=0
dp[2][3]=2
dp[2][4]=2
dp[2][5]=2
dp[3][1]=0
dp[3][2]=0
dp[3][3]=2
dp[3][4]=2
dp[3][5]=3
LCS: 3
How do you reconstruct the actual subsequence?
Start from dp[m][n] and walk backward. If the characters at positions i and j match, that character is part of the LCS; move diagonally. If they do not match, move toward the larger neighbor (up or left).
package com.bank.dsa;
public class ReconstructDemo {
public static String reconstructLCS(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)
? 1 + dp[i - 1][j - 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(reconstructLCS("ABCBDAB", "BDCAB")); // BCAB
}
}
BCAB
How is this different from the Longest Common Substring?
| Aspect | Common Subsequence | Common Substring |
|---|---|---|
| Contiguity | Not required | Required |
| On mismatch | max(top, left) | Reset to 0 |
| Answer location | Corner dp[m][n] | Max anywhere |
| Gaps allowed | Yes | No |
What are the edge cases?
If either string is empty, the LCS is 0. If both are identical, the LCS is their length. If they share no common character, the LCS is 0.
package com.bank.dsa;
public class EdgeCaseDemo {
public static void main(String[] args) {
System.out.println(LongestCommonSubsequence.lcs("", "ABC")); // 0
System.out.println(LongestCommonSubsequence.lcs("ABC", "ABC")); // 3
System.out.println(LongestCommonSubsequence.lcs("ABC", "XYZ")); // 0
}
}
0
3
0
What is the time and space complexity?
Time is O(m*n). Space is O(m*n), reducible to O(min(m,n)) with rolling rows. Reconstruction requires the full table.
What are common interview follow-up questions?
- How would you find the shortest common supersequence?
- How does this relate to the edit distance problem?
- Can you solve this in less than O(m*n) time for special cases?
- How would you count the number of distinct LCS sequences?
Visual Overview
A = "ACE" B = "ABCDE"
DP Table:
"" 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 in corner
Reconstruction (backtrack from dp[3][5]):
E matches E ── include 'E', go diagonal
C matches C ── include 'C', go diagonal
A matches A ── include 'A', go diagonal
LCS = "ACE" (reversed from backtrack)
┌──────────────────────────────────┐
│ Match: 1 + diagonal │
│ Mismatch: max(top, left) │
│ Answer: corner dp[m][n] │
└──────────────────────────────────┘
Key Takeaway
The Longest Common Subsequence finds the longest ordered sequence shared by two strings, allowing gaps. The DP table entry dp[i][j] holds the LCS length of the first i characters of A and the first j characters of B. On a match, add 1 to the diagonal. On a mismatch, carry forward the larger of the cell above or the cell to the left.
Rajesh at the National Bank of India uses this to compare a customer's spending category sequence against a reference lifestyle pattern. The LCS measures how closely the customer follows the reference ordering, even with skipped categories. A high LCS feeds a segmentation model for targeted product offers.
The critical difference from the common substring is that a mismatch never resets to zero. Instead, it carries the best result forward by choosing the larger neighbor. This is why the answer lives in the corner dp[m][n] rather than at some maximum in the middle. Reconstruction walks backward from the corner, stepping diagonally on matches and toward the larger neighbor otherwise.
The time and space are both O(m*n), with space reducible to O(min(m,n)) using rolling rows. Understanding the match-extends-diagonal and mismatch-keeps-best recurrence, and contrasting it with the resetting substring version, is what convinces an interviewer you master both pattern variants.
Remember one sentence: on a match add one to the diagonal, on a mismatch keep the larger neighbor, and the answer is in the corner.
---