Pattern Guide
Shortest Supersequence & LCS Duality
"SCS(s,t) = |s| + |t| - LCS(s,t). Find minimum string containing both as subsequences."
The Shortest Common Supersequence (SCS) is the shortest string that contains both s and t as subsequences. Key formula: |SCS(s,t)| = |s| + |t| - |LCS(s,t)|. To reconstruct SCS: compute LCS, then merge both strings by interleaving. Applications: diff/merge tools, DNA sequence alignment, and string reconstruction problems.
Problems you can solve with this pattern
3 problems · click any to start solving
// Shortest common supersequence length and reconstruction
function scs(s, t) {
const m = s.length, n = t.length;
const dp = Array.from({length: m+1}, () => new Array(n+1).fill(0));
// dp[i][j] = length of SCS of s[0..i-1] and t[0..j-1]
for (let i = 0; i <= m; i++) dp[i][0] = i;
for (let j = 0; j <= n; j++) dp[0][j] = j;
for (let i = 1; i <= m; i++)
for (let j = 1; j <= n; j++)
dp[i][j] = s[i-1] === t[j-1] ? dp[i-1][j-1] + 1
: Math.min(dp[i-1][j], dp[i][j-1]) + 1;
// Reconstruct SCS by tracing back
let i = m, j = n, result = '';
while (i > 0 && j > 0) {
if (s[i-1] === t[j-1]) { result = s[i-1] + result; i--; j--; }
else if (dp[i-1][j] < dp[i][j-1]) { result = s[i-1] + result; i--; }
else { result = t[j-1] + result; j--; }
}
while (i > 0) { result = s[i-1] + result; i--; }
while (j > 0) { result = t[j-1] + result; j--; }
return { length: dp[m][n], scs: result };
}
// Key formula: |SCS(s,t)| = |s| + |t| - |LCS(s,t)|
// This works because LCS characters are shared — they appear once in SCSSCS of s and t: shortest string containing both as subsequences. |SCS| = |s| + |t| - |LCS|, since the LCS characters are shared. To reconstruct: build LCS table, then trace back — when characters match, include once; when they don't, include the character from whichever string DP came from. The result interleaves both strings in minimal fashion.
// Shortest common supersequence length and reconstruction
function scs(s, t) {
const m = s.length, n = t.length;
const dp = Array.from({length: m+1}, () => new Array(n+1).fill(0));
// dp[i][j] = length of SCS of s[0..i-1] and t[0..j-1]
for (let i = 0; i <= m; i++) dp[i][0] = i;
for (let j = 0; j <= n; j++) dp[0][j] = j;
for (let i = 1; i <= m; i++)
for (let j = 1; j <= n; j++)
dp[i][j] = s[i-1] === t[j-1] ? dp[i-1][j-1] + 1
: Math.min(dp[i-1][j], dp[i][j-1]) + 1;
// Reconstruct SCS by tracing back
let i = m, j = n, result = '';
while (i > 0 && j > 0) {
if (s[i-1] === t[j-1]) { result = s[i-1] + result; i--; j--; }
else if (dp[i-1][j] < dp[i][j-1]) { result = s[i-1] + result; i--; }
else { result = t[j-1] + result; j--; }
}
while (i > 0) { result = s[i-1] + result; i--; }
while (j > 0) { result = t[j-1] + result; j--; }
return { length: dp[m][n], scs: result };
}
// Key formula: |SCS(s,t)| = |s| + |t| - |LCS(s,t)|
// This works because LCS characters are shared — they appear once in SCS- |SCS| = |s| + |t| - |LCS|
- Min deletions to make s = t: |s| + |t| - 2×|LCS|
- Min edit distance (insert/delete): |s| + |t| - 2×|LCS|
- LCS = longest common subsequence
- SCS = shortest string containing both as subsequences
Reconstruction: Trace back dp table:
- Characters match: include once, advance both pointers
- Characters differ: include from the direction with smaller dp, advance that pointer
Applications: Version control (git merge/diff), bioinformatics (sequence alignment), patch generation.