PPractick

The problem

You're on a team building a "merge conflict resolver" for a lightweight version-control-like tool. Two collaborators independently edited a shared line of text, producing strings str1 and str2. Instead of forcing a manual merge, your job is to auto-generate the shortest possible merged string such that both str1 and str2 are subsequences of it — meaning both people's edits are "contained" within the merged result without reordering their characters. Return that shortest common supersequence (SCS) string itself, not just its length.

Function signature

string shortestCommonSupersequence(string str1, string str2);

Test cases

str1	str2	One valid output	Explanation
"abac"	"cab"	"cabac"	length 5; both "abac" and "cab" are subsequences of it
"geek"	"eke"	"geeke"	length 5
"abc"	"abc"	"abc"	identical strings → SCS is just the string itself
"abc"	""	"abc"	supersequence of empty string is the other string
""	""	""	trivial
"ab"	"ba"	"aba" or "bab"	length 3, multiple valid answers exist — any correct one is accepted

(Always clarify: many valid SCS strings can exist for the same length — interviewer usually only checks the LENGTH matches optimal, not exact string, unless stated.)

How interviewers phrase it

• "Given two strings, find the shortest string such that both are subsequences of it."
• "Merge two strings into the shortest possible string without breaking either's character order."
• Sometimes asked as a two-parter: "First find the length of the SCS, then actually construct it."

Clarifying questions to ask

1. Do you want just the length of the SCS, or the actual string? (Significantly changes scope — length-only needs just DP values, string needs backtracking/reconstruction.)
2. If multiple shortest supersequences exist, is any valid one acceptable, or do you want a specific one (e.g., lexicographically smallest)?
3. Are the input strings guaranteed non-empty?
4. What's the expected length of the inputs? (Signals whether O(n·m) DP is acceptable or something smarter is needed — for this problem O(n·m) is essentially the expected optimal.)
5. Case-sensitive matching?

Follow-ups to expect

1. "How does this relate to Longest Common Subsequence (LCS)?"
2. "Can you reconstruct the actual SCS string, not just its length?"
3. "Can you optimize space if you only need the length?"
4. "What if you need the SCS for more than two strings?"
5. "What if characters have different insertion costs?"
6. "Can two different SCS strings both be valid answers of minimum length?"

Related questions

• Longest common subsequence Hard
• Print Longest Common Subsequence Hard
• Minimum insertions or deletions to convert string A to B Hard
• Longest common substring Hard
• Longest palindromic subsequence Hard
• Minimum insertions to make string palindrome Hard

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in