Shortest Common Supersequence

🎯

Shortest Common Supersequence

hardDPGoogleAmazon

Imagine merging two versions of a document with minimal redundancy, preserving the order of characters from both versions.

💡 This problem asks for the shortest string containing two given strings as subsequences. Beginners often struggle because it combines understanding subsequences with constructing an actual string, not just computing a length.

📋

Problem Statement

Given two strings str1 and str2, return the shortest string that has both str1 and str2 as subsequences. If multiple answers exist, return any of them.

1 ≤ str1.length, str2.length ≤ 1000str1 and str2 consist of lowercase English letters

💡

Example

Input"str1 = \"abac\", str2 = \"cab\""

Output"cabac"

One shortest common supersequence is "cabac" which contains both "abac" and "cab" as subsequences.

• One string empty → output is the other string
• Both strings identical → output is the string itself
• No common characters → output is concatenation of both strings
• Strings with repeated characters → ensure subsequence order preserved

🔁

Why DP?

Why greedy fails:

A greedy approach that tries to merge characters as soon as they match fails because it may miss shorter supersequences. For example, str1="abac", str2="cab"; greedily picking 'a' first leads to longer supersequence than optimal.

DP state:

dp[i][j] represents the length of the shortest common supersequence of str1[0..i-1] and str2[0..j-1].

Recurrence:If str1[i-1] == str2[j-1], dp[i][j] = 1 + dp[i-1][j-1]; else dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1])

If last chars match, add 1 plus result without those chars; else add 1 plus minimum of removing one char from either string.

⚠️

Common Mistakes

Confusing subsequence with substring

Incorrect results because substring requires contiguous characters

✅ Remember subsequence allows skipping characters, so order matters but not contiguity

Not handling empty string base cases

Index errors or wrong output when one string is empty

✅ Explicitly initialize dp first row and column to handle empty prefixes

Incorrect reconstruction order (not reversing result)

Output string is reversed or scrambled

✅ Build result backwards and reverse at the end

Using string concatenation in recursion without memoization

Excessive time and memory usage, causing TLE

✅ Use memoization or bottom-up DP to avoid recomputation and repeated concatenation

Trying to reconstruct supersequence from space optimized DP

Impossible or very complex reconstruction

✅ Use full 2D DP table if reconstruction is needed

🧠

Brute Force (Pure Recursion)

💡 Starting with brute force helps understand the problem's recursive structure and why naive recursion is inefficient due to repeated subproblems.

Intuition

Try all ways to merge the two strings by recursively choosing characters from either string, building the supersequence step by step.

Algorithm

1. If either string is empty, return the other string as the supersequence.
2. If last characters of both strings match, include it once and recurse on remaining prefixes.
3. Else, recurse by including last character of first string or second string, take the shorter result.
4. Return the shortest supersequence found.

💡 The recursion explores all combinations, which is conceptually simple but computationally expensive.

Recurrence:scs(i,j) = if str1[i-1] == str2[j-1]: 1 + scs(i-1,j-1) else: 1 + min(scs(i-1,j), scs(i,j-1))

</>

Code

def scs(str1, str2):
    def dfs(i, j):
        if i == 0:
            return str2[:j]
        if j == 0:
            return str1[:i]
        if str1[i-1] == str2[j-1]:
            return dfs(i-1, j-1) + str1[i-1]
        else:
            left = dfs(i-1, j) + str1[i-1]
            right = dfs(i, j-1) + str2[j-1]
            return left if len(left) < len(right) else right
    return dfs(len(str1), len(str2))

# Example usage
if __name__ == '__main__':
    print(scs("abac", "cab"))

Line Notes

def dfs(i, j):Defines recursive helper to compute SCS for prefixes of length i and j

if i == 0:Base case: if str1 prefix empty, return str2 prefix

if str1[i-1] == str2[j-1]:If last chars match, include once and recurse on smaller prefixes

return left if len(left) < len(right) else rightChoose shorter supersequence between two recursive options

public class Solution {
    public String shortestCommonSupersequence(String str1, String str2) {
        return dfs(str1, str2, str1.length(), str2.length());
    }
    private String dfs(String s1, String s2, int i, int j) {
        if (i == 0) return s2.substring(0, j);
        if (j == 0) return s1.substring(0, i);
        if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
            return dfs(s1, s2, i - 1, j - 1) + s1.charAt(i - 1);
        } else {
            String left = dfs(s1, s2, i - 1, j) + s1.charAt(i - 1);
            String right = dfs(s1, s2, i, j - 1) + s2.charAt(j - 1);
            return left.length() < right.length() ? left : right;
        }
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.shortestCommonSupersequence("abac", "cab"));
    }
}

Line Notes

private String dfs(String s1, String s2, int i, int j)Recursive helper for prefixes of length i and j

if (i == 0) return s2.substring(0, j);Base case: empty prefix of s1 returns prefix of s2

if (s1.charAt(i - 1) == s2.charAt(j - 1))If last chars match, include once and recurse

return left.length() < right.length() ? left : right;Choose shorter supersequence between two options

#include <iostream>
#include <string>
using namespace std;

string dfs(const string& s1, const string& s2, int i, int j) {
    if (i == 0) return s2.substr(0, j);
    if (j == 0) return s1.substr(0, i);
    if (s1[i - 1] == s2[j - 1]) {
        return dfs(s1, s2, i - 1, j - 1) + s1[i - 1];
    } else {
        string left = dfs(s1, s2, i - 1, j) + s1[i - 1];
        string right = dfs(s1, s2, i, j - 1) + s2[j - 1];
        return (left.size() < right.size()) ? left : right;
    }
}

int main() {
    cout << dfs("abac", "cab", 4, 3) << endl;
    return 0;
}

Line Notes

string dfs(const string& s1, const string& s2, int i, int j)Recursive function for prefixes of s1 and s2

if (i == 0) return s2.substr(0, j);Base case: empty s1 prefix returns s2 prefix

if (s1[i - 1] == s2[j - 1])If last chars match, include once and recurse

return (left.size() < right.size()) ? left : right;Pick shorter supersequence between two recursive calls

function scs(str1, str2) {
  function dfs(i, j) {
    if (i === 0) return str2.slice(0, j);
    if (j === 0) return str1.slice(0, i);
    if (str1[i - 1] === str2[j - 1]) {
      return dfs(i - 1, j - 1) + str1[i - 1];
    } else {
      const left = dfs(i - 1, j) + str1[i - 1];
      const right = dfs(i, j - 1) + str2[j - 1];
      return left.length < right.length ? left : right;
    }
  }
  return dfs(str1.length, str2.length);
}

console.log(scs("abac", "cab"));

Line Notes

function dfs(i, j)Recursive helper for prefixes of length i and j

if (i === 0) return str2.slice(0, j);Base case: empty prefix of str1 returns prefix of str2

if (str1[i - 1] === str2[j - 1])If last chars match, include once and recurse

return left.length < right.length ? left : right;Choose shorter supersequence between two recursive options

⏱

Complexity

TimeO(2^(m+n))

SpaceO(m+n) recursion stack

Each call branches into two except when chars match, leading to exponential calls.

💡 For strings of length 10, this could mean over a million calls, which is impractical.

Interview Verdict: TLE

This approach is too slow for large inputs but is essential to understand problem structure.

🧠

Top-Down Memoization

💡 Memoization caches results of recursive calls to avoid recomputation, drastically improving efficiency.

Intuition

Store results of subproblems (prefix pairs) so each is computed once, turning exponential recursion into polynomial time.

Algorithm

1. Initialize a memo dictionary to store results for (i, j) pairs.
2. If either string prefix is empty, return the other prefix.
3. If last chars match, recurse on smaller prefixes and append the char.
4. Else, recurse on both options, store and return the shorter supersequence.

💡 Memoization avoids repeated work by caching results, making recursion feasible for larger inputs.

Recurrence:Same as brute force: scs(i,j) = if chars equal: 1 + scs(i-1,j-1) else 1 + min(scs(i-1,j), scs(i,j-1))

</>

Code

def scs(str1, str2):
    memo = {}
    def dfs(i, j):
        if (i, j) in memo:
            return memo[(i, j)]
        if i == 0:
            memo[(i, j)] = str2[:j]
            return memo[(i, j)]
        if j == 0:
            memo[(i, j)] = str1[:i]
            return memo[(i, j)]
        if str1[i-1] == str2[j-1]:
            memo[(i, j)] = dfs(i-1, j-1) + str1[i-1]
        else:
            left = dfs(i-1, j) + str1[i-1]
            right = dfs(i, j-1) + str2[j-1]
            memo[(i, j)] = left if len(left) < len(right) else right
        return memo[(i, j)]
    return dfs(len(str1), len(str2))

if __name__ == '__main__':
    print(scs("abac", "cab"))

Line Notes

memo = {}Initialize cache to store results for subproblems

if (i, j) in memo:Return cached result if available to avoid recomputation

memo[(i, j)] = dfs(i-1, j-1) + str1[i-1]Store result when last chars match

memo[(i, j)] = left if len(left) < len(right) else rightStore shorter supersequence result for mismatched chars

import java.util.*;
public class Solution {
    Map<String, String> memo = new HashMap<>();
    public String shortestCommonSupersequence(String str1, String str2) {
        return dfs(str1, str2, str1.length(), str2.length());
    }
    private String dfs(String s1, String s2, int i, int j) {
        String key = i + "," + j;
        if (memo.containsKey(key)) return memo.get(key);
        if (i == 0) {
            memo.put(key, s2.substring(0, j));
            return memo.get(key);
        }
        if (j == 0) {
            memo.put(key, s1.substring(0, i));
            return memo.get(key);
        }
        if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
            memo.put(key, dfs(s1, s2, i - 1, j - 1) + s1.charAt(i - 1));
        } else {
            String left = dfs(s1, s2, i - 1, j) + s1.charAt(i - 1);
            String right = dfs(s1, s2, i, j - 1) + s2.charAt(j - 1);
            memo.put(key, left.length() < right.length() ? left : right);
        }
        return memo.get(key);
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.shortestCommonSupersequence("abac", "cab"));
    }
}

Line Notes

Map<String, String> memo = new HashMap<>();Cache results for subproblems using string keys

String key = i + "," + j;Create unique key for current subproblem

if (memo.containsKey(key)) return memo.get(key);Return cached result if present

memo.put(key, left.length() < right.length() ? left : right);Store shorter supersequence result

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

unordered_map<string, string> memo;

string dfs(const string& s1, const string& s2, int i, int j) {
    string key = to_string(i) + "," + to_string(j);
    if (memo.count(key)) return memo[key];
    if (i == 0) return memo[key] = s2.substr(0, j);
    if (j == 0) return memo[key] = s1.substr(0, i);
    if (s1[i - 1] == s2[j - 1]) {
        return memo[key] = dfs(s1, s2, i - 1, j - 1) + s1[i - 1];
    } else {
        string left = dfs(s1, s2, i - 1, j) + s1[i - 1];
        string right = dfs(s1, s2, i, j - 1) + s2[j - 1];
        return memo[key] = (left.size() < right.size()) ? left : right;
    }
}

int main() {
    cout << dfs("abac", "cab", 4, 3) << endl;
    return 0;
}

Line Notes

unordered_map<string, string> memo;Cache subproblem results with string keys

string key = to_string(i) + "," + to_string(j);Unique key for current subproblem

if (memo.count(key)) return memo[key];Return cached result if exists

return memo[key] = (left.size() < right.size()) ? left : right;Store and return shorter supersequence

function scs(str1, str2) {
  const memo = new Map();
  function dfs(i, j) {
    const key = i + ',' + j;
    if (memo.has(key)) return memo.get(key);
    if (i === 0) {
      memo.set(key, str2.slice(0, j));
      return memo.get(key);
    }
    if (j === 0) {
      memo.set(key, str1.slice(0, i));
      return memo.get(key);
    }
    if (str1[i - 1] === str2[j - 1]) {
      memo.set(key, dfs(i - 1, j - 1) + str1[i - 1]);
    } else {
      const left = dfs(i - 1, j) + str1[i - 1];
      const right = dfs(i, j - 1) + str2[j - 1];
      memo.set(key, left.length < right.length ? left : right);
    }
    return memo.get(key);
  }
  return dfs(str1.length, str2.length);
}

console.log(scs("abac", "cab"));

Line Notes

const memo = new Map();Cache results for subproblems

const key = i + ',' + j;Unique key for memoization

if (memo.has(key)) return memo.get(key);Return cached result if available

memo.set(key, left.length < right.length ? left : right);Store shorter supersequence result

⏱

Complexity

TimeO(m*n * (m+n))

SpaceO(m*n * (m+n)) due to memo storing strings

Each subproblem computed once, but concatenation of strings costs extra time and space.

💡 Memoization reduces calls drastically but string concatenation can still be costly.

Interview Verdict: Accepted but can be optimized

Memoization makes solution feasible but not optimal due to string concatenation overhead.

🧠

Bottom-Up DP with Reconstruction

💡 Tabulation builds the solution iteratively and allows reconstructing the shortest common supersequence efficiently.

Intuition

Compute lengths of shortest supersequences for all prefixes, then reconstruct the answer by tracing decisions.

Algorithm

1. Initialize dp table of size (m+1) x (n+1) with base cases.
2. Fill dp[i][j] using recurrence: if chars match, 1 + dp[i-1][j-1], else 1 + min(dp[i-1][j], dp[i][j-1]).
3. After filling dp, reconstruct the supersequence by tracing from dp[m][n] backwards.
4. Append characters accordingly to build the shortest common supersequence.

💡 Tabulation avoids recursion overhead and makes reconstruction straightforward by storing lengths.

Recurrence:dp[i][j] = if str1[i-1] == str2[j-1]: 1 + dp[i-1][j-1] else 1 + min(dp[i-1][j], dp[i][j-1])

</>

Code

def scs(str1, str2):
    m, n = len(str1), len(str2)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(m+1):
        dp[i][0] = i
    for j in range(n+1):
        dp[0][j] = j
    for i in range(1, m+1):
        for j in range(1, n+1):
            if str1[i-1] == str2[j-1]:
                dp[i][j] = 1 + dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1])
    i, j = m, n
    res = []
    while i > 0 and j > 0:
        if str1[i-1] == str2[j-1]:
            res.append(str1[i-1])
            i -= 1
            j -= 1
        elif dp[i-1][j] < dp[i][j-1]:
            res.append(str1[i-1])
            i -= 1
        else:
            res.append(str2[j-1])
            j -= 1
    while i > 0:
        res.append(str1[i-1])
        i -= 1
    while j > 0:
        res.append(str2[j-1])
        j -= 1
    return ''.join(reversed(res))

if __name__ == '__main__':
    print(scs("abac", "cab"))

Line Notes

dp = [[0]*(n+1) for _ in range(m+1)]Create DP table for all prefix pairs

dp[i][0] = iBase case: shortest supersequence with empty str2 is str1 prefix

if str1[i-1] == str2[j-1]:If chars match, add 1 plus diagonal value

while i > 0 and j > 0:Reconstruct supersequence by tracing decisions backwards

public class Solution {
    public String shortestCommonSupersequence(String str1, String str2) {
        int m = str1.length(), n = str2.length();
        int[][] dp = new int[m+1][n+1];
        for (int i = 0; i <= m; i++) dp[i][0] = i;
        for (int j = 0; j <= n; j++) dp[0][j] = j;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (str1.charAt(i-1) == str2.charAt(j-1)) {
                    dp[i][j] = 1 + dp[i-1][j-1];
                } else {
                    dp[i][j] = 1 + Math.min(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        int i = m, j = n;
        while (i > 0 && j > 0) {
            if (str1.charAt(i-1) == str2.charAt(j-1)) {
                sb.append(str1.charAt(i-1));
                i--; j--;
            } else if (dp[i-1][j] < dp[i][j-1]) {
                sb.append(str1.charAt(i-1));
                i--;
            } else {
                sb.append(str2.charAt(j-1));
                j--;
            }
        }
        while (i > 0) sb.append(str1.charAt(i - 1)); i--;
        while (j > 0) sb.append(str2.charAt(j - 1)); j--;
        return sb.reverse().toString();
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.shortestCommonSupersequence("abac", "cab"));
    }
}

Line Notes

int[][] dp = new int[m+1][n+1];DP table for prefix pairs lengths

dp[i][0] = i;Base case: supersequence length when second string empty

if (str1.charAt(i-1) == str2.charAt(j-1))If chars match, add 1 plus diagonal

while (i > 0 && j > 0)Trace back to reconstruct supersequence

while (i > 0) sb.append(str1.charAt(i - 1)); i--;Append remaining characters from str1 after main loop

while (j > 0) sb.append(str2.charAt(j - 1)); j--;Append remaining characters from str2 after main loop

#include <iostream>
#include <string>
#include <vector>
using namespace std;

string scs(const string& str1, const string& str2) {
    int m = str1.size(), n = str2.size();
    vector<vector<int>> dp(m+1, vector<int>(n+1));
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (str1[i-1] == str2[j-1]) {
                dp[i][j] = 1 + dp[i-1][j-1];
            } else {
                dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    string res;
    int i = m, j = n;
    while (i > 0 && j > 0) {
        if (str1[i-1] == str2[j-1]) {
            res.push_back(str1[i-1]);
            i--; j--;
        } else if (dp[i-1][j] < dp[i][j-1]) {
            res.push_back(str1[i-1]);
            i--;
        } else {
            res.push_back(str2[j-1]);
            j--;
        }
    }
    while (i > 0) res.push_back(str1[i-1]), i--;
    while (j > 0) res.push_back(str2[j-1]), j--;
    reverse(res.begin(), res.end());
    return res;
}

int main() {
    cout << scs("abac", "cab") << endl;
    return 0;
}

Line Notes

vector<vector<int>> dp(m+1, vector<int>(n+1));DP table for lengths of shortest supersequences

dp[i][0] = i;Base case for empty second string

if (str1[i-1] == str2[j-1])If chars match, add 1 plus diagonal

while (i > 0 && j > 0)Reconstruct supersequence by tracing decisions

function scs(str1, str2) {
  const m = str1.length, n = str2.length;
  const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
  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++) {
      if (str1[i - 1] === str2[j - 1]) {
        dp[i][j] = 1 + dp[i - 1][j - 1];
      } else {
        dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }
  let i = m, j = n;
  const res = [];
  while (i > 0 && j > 0) {
    if (str1[i - 1] === str2[j - 1]) {
      res.push(str1[i - 1]);
      i--;
      j--;
    } else if (dp[i - 1][j] < dp[i][j - 1]) {
      res.push(str1[i - 1]);
      i--;
    } else {
      res.push(str2[j - 1]);
      j--;
    }
  }
  while (i > 0) res.push(str1[i - 1]), i--;
  while (j > 0) res.push(str2[j - 1]), j--;
  return res.reverse().join('');
}

console.log(scs("abac", "cab"));

Line Notes

const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));Create 2D DP array for prefix pairs

dp[i][0] = i;Base case: shortest supersequence length with empty second string

if (str1[i - 1] === str2[j - 1])If chars match, add 1 plus diagonal

while (i > 0 && j > 0)Trace back to reconstruct shortest supersequence

⏱

Complexity

TimeO(m*n)

SpaceO(m*n)

Fills dp table once and reconstructs answer in O(m+n).

💡 For strings of length 1000, this is about 1 million operations, which is efficient.

Interview Verdict: Accepted and optimal for length and construction

This approach is the standard solution to implement in interviews.

🧠

Space Optimized Bottom-Up DP

💡 We optimize space by storing only two rows of the DP table at a time, since each dp[i][j] depends only on previous row and current row.

Intuition

Since dp[i][j] depends on dp[i-1][j-1], dp[i-1][j], and dp[i][j-1], we can keep track of only two rows and reconstruct the length efficiently.

Algorithm

1. Initialize two 1D arrays to represent previous and current dp rows.
2. Iterate through str1 and str2, filling current row based on previous row and current row values.
3. After filling, the last element of current row is the length of shortest supersequence.
4. Note: Reconstruction is complex with this optimization and usually not done.

💡 This approach reduces memory usage but sacrifices easy reconstruction of the supersequence.

Recurrence:Same as tabulation but stored in 1D arrays: dp[j] = if chars equal: 1 + prev[j-1] else 1 + min(prev[j], dp[j-1])

</>

Code

def scs_length(str1, str2):
    m, n = len(str1), len(str2)
    prev = list(range(n+1))
    for i in range(1, m+1):
        curr = [i] + [0]*n
        for j in range(1, n+1):
            if str1[i-1] == str2[j-1]:
                curr[j] = 1 + prev[j-1]
            else:
                curr[j] = 1 + min(prev[j], curr[j-1])
        prev = curr
    return prev[n]

if __name__ == '__main__':
    print(scs_length("abac", "cab"))

Line Notes

prev = list(range(n+1))Initialize dp for empty str1 prefix

curr = [i] + [0]*nInitialize current row with base case for empty str2 prefix

if str1[i-1] == str2[j-1]:If chars match, add 1 plus diagonal (prev[j-1])

prev = currUpdate previous row to current for next iteration

public class Solution {
    public int scsLength(String str1, String str2) {
        int m = str1.length(), n = str2.length();
        int[] prev = new int[n+1];
        for (int j = 0; j <= n; j++) prev[j] = j;
        for (int i = 1; i <= m; i++) {
            int[] curr = new int[n+1];
            curr[0] = i;
            for (int j = 1; j <= n; j++) {
                if (str1.charAt(i-1) == str2.charAt(j-1)) {
                    curr[j] = 1 + prev[j-1];
                } else {
                    curr[j] = 1 + Math.min(prev[j], curr[j-1]);
                }
            }
            prev = curr;
        }
        return prev[n];
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.scsLength("abac", "cab"));
    }
}

Line Notes

int[] prev = new int[n+1];Store previous dp row

curr[0] = i;Base case for empty second string prefix

if (str1.charAt(i-1) == str2.charAt(j-1))If chars match, add 1 plus diagonal

prev = curr;Update previous row for next iteration

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int scsLength(const string& str1, const string& str2) {
    int m = str1.size(), n = str2.size();
    vector<int> prev(n+1);
    for (int j = 0; j <= n; j++) prev[j] = j;
    for (int i = 1; i <= m; i++) {
        vector<int> curr(n+1);
        curr[0] = i;
        for (int j = 1; j <= n; j++) {
            if (str1[i-1] == str2[j-1]) {
                curr[j] = 1 + prev[j-1];
            } else {
                curr[j] = 1 + min(prev[j], curr[j-1]);
            }
        }
        prev = curr;
    }
    return prev[n];
}

int main() {
    cout << scsLength("abac", "cab") << endl;
    return 0;
}

Line Notes

vector<int> prev(n+1);Previous dp row storage

curr[0] = i;Base case for empty second string prefix

if (str1[i-1] == str2[j-1])If chars match, add 1 plus diagonal

prev = curr;Update previous row for next iteration

function scsLength(str1, str2) {
  const m = str1.length, n = str2.length;
  let prev = Array(n + 1).fill(0).map((_, i) => i);
  for (let i = 1; i <= m; i++) {
    let curr = Array(n + 1).fill(0);
    curr[0] = i;
    for (let j = 1; j <= n; j++) {
      if (str1[i - 1] === str2[j - 1]) {
        curr[j] = 1 + prev[j - 1];
      } else {
        curr[j] = 1 + Math.min(prev[j], curr[j - 1]);
      }
    }
    prev = curr;
  }
  return prev[n];
}

console.log(scsLength("abac", "cab"));

Line Notes

let prev = Array(n + 1).fill(0).map((_, i) => i);Initialize dp for empty str1 prefix

curr[0] = i;Base case for empty str2 prefix

if (str1[i - 1] === str2[j - 1])If chars match, add 1 plus diagonal

prev = curr;Update previous row for next iteration

⏱

Complexity

TimeO(m*n)

SpaceO(n)

Only two rows stored, reducing space from O(m*n) to O(n).

💡 For large strings, this saves significant memory while keeping time efficient.

Interview Verdict: Accepted for length only; reconstruction not supported

Use when only length is needed or memory is constrained; otherwise use full DP for reconstruction.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, implement bottom-up DP with reconstruction for full solution; mention brute force and memoization to show understanding.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^(m+n))	O(m+n) recursion stack	Yes (deep recursion)	Yes (implicit in recursion)	Mention only - never code
2. Top-Down Memoization	O(m*n * (m+n))	O(m*n * (m+n)) due to string storage	No (memoization limits calls)	Yes (cached strings)	Good to mention, but not optimal to code
3. Bottom-Up DP with Reconstruction	O(m*n)	O(m*n)	No	Yes	Code this approach in interviews
4. Space Optimized Bottom-Up DP	O(m*n)	O(n)	No	No	Mention if asked about space optimization

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and know when to optimize or reconstruct solutions.

How to Present

Clarify problem requirements and constraints.Explain brute force recursion to show understanding of problem structure.Introduce memoization to optimize overlapping subproblems.Present bottom-up DP with reconstruction as optimal solution.Mention space optimization if interviewer asks about memory.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test: 5min. Total ~20min

What the Interviewer Tests

Understanding of DP concepts, ability to optimize naive solutions, and skill in reconstructing solutions from DP tables.

Common Follow-ups

• Can you optimize space usage? → Use 1D DP arrays
• How to reconstruct the actual supersequence? → Trace back from dp table

💡 These follow-ups test deeper DP knowledge and coding skills beyond just computing length.

🔍

Pattern Recognition

When to Use

1) Asked for shortest string containing two strings as subsequences; 2) Problem involves two strings and subsequence constraints; 3) Overlapping subproblems with prefix pairs; 4) Requires construction of solution, not just length.

Signature Phrases

shortest string containing both strings as subsequencesreturn any valid shortest supersequence

NOT This Pattern When

Shortest Common Superstring - requires substring concatenation, not subsequence

Similar Problems

Longest Common Subsequence - helps compute length for SCSEdit Distance - related string transformation problem

Practice

1. Consider the following Python code that counts palindromic substrings using the expand around center approach. What is the final returned count when the input string is "aaa"?

def countSubstrings(s: str) -> int:
    n = len(s)
    count = 0

    def expand(left, right):
        nonlocal count
        while left >= 0 and right < n and s[left] == s[right]:
            count += 1
            left -= 1
            right += 1

    for i in range(n):
        expand(i, i)      # Odd length palindromes
        expand(i, i + 1)  # Even length palindromes

    return count

print(countSubstrings('aaa'))  # ?

easy

A. 3

B. 6

C. 4

D. 5

Solution

1. Step 1: Trace expansions for i=0

   expand(0,0) counts 'a' -> count=1; expand(0,1) counts 'aa' -> count=2

2. Step 2: Trace expansions for i=1 and i=2

   i=1: expand(1,1) counts 'a', 'aaa' -> +2; expand(1,2) counts 'aa' -> +1; i=2: expand(2,2) counts 'a' -> +1; total count=6

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   All palindromic substrings: 'a', 'a', 'a', 'aa', 'aa', 'aaa' [OK]

Hint: Count includes all odd and even length palindromes [OK]

Common Mistakes:

• Counting only single characters or missing even length palindromes

2. What is the time complexity of the optimal expand around center approach for counting palindromic substrings in a string of length n?

medium

A. O(n²)

B. O(n)

C. O(n³)

D. O(n log n)

Solution

1. Step 1: Identify loops in the algorithm

   Outer loop runs n times; for each center, expansion can take up to O(n) steps.

2. Step 2: Calculate total complexity

   Each of the n centers expands up to n steps -> total O(n²). No nested triple loops or recursion stack adds more.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two nested loops or expansions -> quadratic time [OK]

Hint: Two nested loops or expansions -> O(n²) time [OK]

Common Mistakes:

• Confusing with brute force O(n³) or assuming linear time

3. What is the time complexity of the space-optimized bottom-up DP solution for the longest common substring problem, where n and m are the lengths of the two input strings?

medium

A. O(n * m) due to nested loops comparing all character pairs

B. O(n * m) but with additional O(n + m) recursion stack space

C. O(n * m * min(n, m)) due to checking all substrings explicitly

D. O(n + m) due to single pass over both strings

Solution

1. Step 1: Identify nested loops over n and m

   The algorithm uses two nested loops: outer over n and inner over m, leading to O(n*m) iterations.

2. Step 2: Confirm no recursion or substring extraction

   Space optimization uses iterative DP with O(m) space, no recursion stack or substring extraction, so no extra multiplicative factors.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Nested loops over both strings dominate time complexity [OK]

Hint: Nested loops over both strings imply O(n*m) time [OK]

Common Mistakes:

• Confusing with linear O(n+m)
• Assuming recursion adds stack space
• Thinking substring extraction adds extra factor

4. Suppose you want to count palindromic substrings in a string where characters can be replaced any number of times (reusable characters). Which modification to the expand around center approach correctly handles this variant?

hard

A. No modification needed; the original expand around center approach already counts palindromes with replacements.

B. Modify expand to allow skipping mismatched characters to find palindromes with replacements.

C. Precompute all possible character replacements and run the original expand around center for each variant.

D. Use dynamic programming with memoization to store counts for substrings allowing character replacements.

Solution

1. Step 1: Understand the variant

   Allowing character replacements means palindrome checks must consider substitutions, not exact matches.

2. Step 2: Evaluate approaches

   Expand around center relies on exact matches; skipping mismatches breaks palindrome definition. Precomputing all variants is exponential. DP with memoization can track allowed replacements efficiently.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   DP can handle flexible palindrome definitions with substitutions [OK]

Hint: Exact match expansion fails when replacements allowed [OK]

Common Mistakes:

• Assuming original approach works without changes

5. Suppose you want to find the longest palindromic subsequence in a string where characters can be reused unlimited times. Which modification to the DP approach correctly handles this variant?

hard

A. Modify DP to consider infinite reuse by allowing i to stay fixed while j moves, and vice versa

B. Use a greedy approach selecting matching characters repeatedly from both ends

C. Use the same DP but allow indices i and j to move independently without restriction

D. This problem reduces to longest palindromic substring, so use Manacher's algorithm

Solution

1. Step 1: Understand reuse means characters can be counted multiple times

   Standard LPS counts each character once; reuse requires relaxing index movement constraints.

2. Step 2: Modify DP transitions to allow staying at i or j to reuse characters

   DP must consider cases where i or j does not advance to reuse characters, effectively allowing repeated use.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Allowing indices to stay or move independently models reuse correctly [OK]

Hint: Reuse means relaxing index movement in DP transitions [OK]

Common Mistakes:

• Using greedy approach
• Confusing substring with subsequence
• Applying substring algorithms incorrectly