Shortest Common Supersequence

// 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