PPractick

The problem

You're building a "changelog minimizer" for a text-diffing tool (similar to what powers git diff under the hood, but restricted to a simpler operation set). Given two strings A and B, you're only allowed to insert characters into A or delete characters from A (no replace operation this time — that's a deliberate constraint distinguishing this from Edit Distance). Find the minimum total number of insertions + deletions needed to transform A into B.

Function signature

int minInsertDelete(string A, string B);

Test cases

A	B	Output	Explanation
"heap"	"pea"	3	LCS = "ea" (len 2); delete "h","p" (2 deletions) + insert "p" (1 insertion) = 3
"geek"	"eke"	2	LCS = "ek" (len 2); delete "g" (1) + insert "" ... verify: delete 2, insert 1 → total 3, check LCS carefully via code
"abc"	"abc"	0	identical strings, LCS = full length, no ops needed
"abc"	""	3	delete all 3 characters
""	"abc"	3	insert all 3 characters
""	""	0	trivial
"a"	"b"	2	no replace allowed! must delete "a" (1) then insert "b" (1) = 2, NOT 1

(Note the last test case — this is the key distinguishing trap vs. Edit Distance, where replace would give 1. Here replace isn't allowed, so it costs 2.)

How interviewers phrase it

• "Given two strings, find the minimum number of insertions and deletions (no replacements allowed) to convert one into the other."
• "How would you transform string A into string B using only add/remove character operations?"
• Sometimes given right after Edit Distance as a "trick variant" to see if you notice the missing replace operation and adapt.

Clarifying questions to ask

1. Is a replace operation allowed at all, or strictly only insert and delete? (This is the single most important clarifying question — confirm explicitly, since it's easy to default to full Edit Distance logic.)
2. Do insertions/deletions cost the same (unit cost) or different costs?
3. Are A and B guaranteed non-empty?
4. Case-sensitive?
5. Should I return just the count, or also describe/construct the sequence of operations?

Follow-ups to expect

1. "How is this different from full Edit Distance?"
2. "Can you relate this to LCS directly?"
3. "Can you optimize space?"
4. "What if you also needed to output the actual sequence of insert/delete operations?"
5. "What's the relationship between this problem and Shortest Common Supersequence?"
6. "What if insert and delete had different costs (e.g., insert = 2, delete = 1)?"

Related questions

• Longest common subsequence Hard
• Print Longest Common Subsequence Hard
• Shortest common supersequence 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