Definition
- Shortest Common Supersequence (SCS) – the shortest string that contains both input strings as subsequences.
- Formula –
SCS length = len(A) + len(B) - LCS(A, B), because the LCS characters are shared and written only once. - LCS computation – use the standard 2D DP table where match copies diagonal+1 and mismatch takes max(top, left).
- Reconstruction – walk the DP table from dp[m][n]; on match, emit the character once; on mismatch, emit from the side you move toward.
- Complexity – O(m * n) time and space for the LCS table.
The National Bank of India merges two partial transaction logs from different nodes into one combined log that preserves the order of both. Shared events are written only once, and unique events from each side are interleaved. The shortest such combined log has length equal to the two lengths minus their longest shared ordered overlap.
Understanding the Concepts
What is the Shortest Common Supersequence?
A common supersequence of two strings is a string that contains both as subsequences. The shortest common supersequence (SCS) is the shortest such string. For example, for "ABAC" and "CAB", one SCS is "CABAC" with length 5.
package com.bank.core;
// A = "ABAC", B = "CAB"
// SCS: "CABAC" (length 5)
// Check: "ABAC" is a subsequence of "CABAC"? A(1),B(2),A(3),C(4) -> yes
// Check: "CAB" is a subsequence of "CABAC"? C(0),A(1),B(2) -> yes
Why does SCS length equal len(A) + len(B) - LCS?
A supersequence must include every character of both strings in their original order. The only characters that can overlap between the two strings and be written a single time are those forming a common subsequence. To minimize the length, we maximize the overlap, which is the longest common subsequence. Every other character is unique to one string and must appear separately. So SCS = len(A) + len(B) - LCS.
package com.bank.core;
// A = "ABAC" (length 4), B = "CAB" (length 3)
// LCS of A and B: "AB" (length 2)
// SCS length = 4 + 3 - 2 = 5
// The LCS characters "AB" are shared, written once
// Remaining: "AC" from A and "C" from B are unique
How do you compute the SCS length?
First compute the LCS using the standard 2D DP table, then apply the formula. The LCS table is the one where match gives diagonal+1 and mismatch gives max(top, left).
package com.bank.service;
public class ShortestCommonSupersequence {
public int scsLength(String a, String b) {
int lcsLen = lcs(a, b);
return a.length() + b.length() - lcsLen;
}
private int lcs(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) {
ShortestCommonSupersequence solver = new ShortestCommonSupersequence();
System.out.println(solver.scsLength("ABAC", "CAB"));
System.out.println(solver.scsLength("TRANSFER", "TRANSFORM"));
}
}
5
10
How do you reconstruct the actual SCS string?
Walk the LCS DP table from dp[m][n] back to dp[0][0]. When the characters match, emit the character once and move diagonally. When they differ, emit the character from the side with the larger DP value and move toward it. After reaching the border, emit any remaining characters from the unfinished string.
package com.bank.service;
public class SCSReconstructor {
public String findSCS(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]);
}
}
}
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]) {
sb.append(a.charAt(i - 1));
i--;
} else {
sb.append(b.charAt(j - 1));
j--;
}
}
while (i > 0) { sb.append(a.charAt(i - 1)); i--; }
while (j > 0) { sb.append(b.charAt(j - 1)); j--; }
return sb.reverse().toString();
}
public static void main(String[] args) {
SCSReconstructor solver = new SCSReconstructor();
System.out.println(solver.findSCS("ABAC", "CAB"));
}
}
CABAC
How is SCS related to LCS and Edit Distance?
SCS, LCS, and Edit Distance are all members of the Longest Common Substring pattern family. They share the same 2D DP table structure but answer different questions about the relationship between two strings.
| Problem | Formula/Answer | Uses LCS table |
|---|---|---|
| LCS length | dp[m][n] | Directly |
| SCS length | m + n - LCS | Subtract LCS from total |
| Edit distance (insert/delete) | m + n - 2 * LCS | Two-way complement |
| Edit distance (with substitution) | Own recurrence | Related but separate |
package com.bank.core;
// All three use the same 2D DP table structure
// LCS: match -> diagonal+1, mismatch -> max(top,left)
// SCS: len(A) + len(B) - LCS
// Edit distance (insert/delete only): len(A) + len(B) - 2*LCS
What are the edge cases?
Edge cases include: one string is empty (SCS is the other string), both strings are identical (SCS is the string itself), one string is a subsequence of the other (SCS is the longer string), and strings with no common characters (SCS is their concatenation).
package com.bank.core;
// Edge case 1: A="", B="ABC" -> SCS = "ABC" (len=3)
// Edge case 2: A=B="ABC" -> LCS=3, SCS=3+3-3=3 ("ABC")
// Edge case 3: A="AC", B="ABC" -> A is subsequence of B, SCS = B (len=3)
// Edge case 4: A="XY", B="AB" -> no common chars, SCS = "XYAB" or "ABXY" (len=4)
What about a banking use case?
At the National Bank of India, two branch servers capture partial transaction logs. The compliance team merges them into one combined log that preserves both orderings while writing shared events only once.
package com.bank.service;
public class LogMerger {
private final SCSReconstructor solver = new SCSReconstructor();
public String mergeLogs(String log1, String log2) {
String merged = solver.findSCS(log1, log2);
System.out.println("Log 1: " + log1);
System.out.println("Log 2: " + log2);
System.out.println("Merged: " + merged + " (length " + merged.length() + ")");
return merged;
}
public static void main(String[] args) {
LogMerger merger = new LogMerger();
merger.mergeLogs("DWTD", "DWSD");
}
}
Log 1: DWTD
Log 2: DWSD
Merged: DWSTD (length 5)
What are common mistakes?
The most common mistake is forgetting to handle the remaining characters after one pointer reaches zero during reconstruction. Another mistake is confusing SCS with LCS and using the wrong formula.
package com.bank.core;
// WRONG: forgetting remaining characters
while (i > 0 && j > 0) { /* ... */ }
// Missing: while (i > 0) append a[i-1]
// Missing: while (j > 0) append b[j-1]
// CORRECT: handle remaining after main loop
while (i > 0) { sb.append(a.charAt(i-1)); i--; }
while (j > 0) { sb.append(b.charAt(j-1)); j--; }
What should a senior engineer know?
A senior engineer should know that SCS is the natural complement of LCS, and computing one immediately gives the other. The reconstruction walk is the same as LCS reconstruction but emits characters from both sides instead of only matching characters. For length-only computation, the rolling-row optimization reduces space to O(min(m, n)), but reconstruction requires the full table.
package com.bank.core;
// Senior notes:
// 1. SCS = complement of LCS: same table, different interpretation
// 2. Reconstruction: emit from both sides, not just matches
// 3. Space optimization: O(min(m,n)) for length, O(m*n) for reconstruction
// 4. Time: O(m*n) dominated by LCS computation
// 5. Practical use: merge sorted logs, combine partial sequences
Visual Overview
SCS computation for A = "ABAC", B = "CAB":
Step 1: Compute LCS table
"" C A B
"" [ 0 0 0 0 ]
A [ 0 0 1 1 ]
B [ 0 0 1 2 ]
A [ 0 0 1 2 ]
C [ 0 1 1 2 ]
LCS length = dp[4][3] = 2 ("AB")
SCS length = 4 + 3 - 2 = 5
Step 2: Reconstruct SCS by walking the table
i=4, j=3: A[3]='C', B[2]='B' -> differ
dp[3][3]=2 vs dp[4][2]=1 -> go up, emit 'C'
i=3, j=3: A[2]='A', B[2]='B' -> differ
dp[2][3]=2 vs dp[3][2]=1 -> go up, emit 'A'
i=2, j=3: A[1]='B', B[2]='B' -> match!
emit 'B', move diagonal
i=1, j=2: A[0]='A', B[1]='A' -> match!
emit 'A', move diagonal
i=0, j=1: remaining B[0]='C'
emit 'C'
Collected (reversed): C, A, B, A, C -> "CABAC"
Key Takeaway
The Shortest Common Supersequence is the natural complement of the Longest Common Subsequence. A supersequence must contain both strings as subsequences, meaning it includes every character of both while preserving each string's order. The only characters that can be shared and written once are those in the LCS, so the shortest length is len(A) + len(B) - LCS.
You compute the LCS with the standard 2D DP table and apply the formula for the length. To reconstruct the actual supersequence, you walk the table from dp[m][n] back to the origin. On a character match, emit it once and move diagonally. On a mismatch, emit the character from the side with the larger DP value and move toward it. After reaching the border, emit any remaining characters from the unfinished string.
SCS, LCS, and edit distance all belong to the same Longest Common Substring pattern family. Computing one gives you the tools to compute the others. The space is O(m * n) for the full table needed for reconstruction, though length-only computation can use a rolling row for O(min(m, n)) space.
At the National Bank of India, Rajesh used SCS to merge two partial transaction logs from different branch servers into one compact combined log that preserved both orderings while writing shared events only once. The LCS table identified the shared events, and the reconstruction walk interleaved the unique events correctly.
Remember one sentence: the shortest common supersequence length equals the sum of both string lengths minus their longest common subsequence length.
---