📘 Minimum Insertions and Deletions to Convert String A -B

🔹 Problem

Given two strings:

s1 → convert into → s2

👉 Find:

• Minimum deletions
• Minimum insertions

---

🔥 Key Idea (VERY IMPORTANT)

👉 Use Longest Common Subsequence (LCS)

Let L = LCS(s1, s2)

---

🔹 Formula

Deletions = n - L
Insertions = m - L

Where:

• n = length of s1
• m = length of s2

---

🧠 Why this works?

• LCS = part already common → no need to change
• Remove extra from s1 → deletions
• Add missing for s2 → insertions

---

🔹 Example

s1 = "heap"
s2 = "pea"

👉 LCS = "ea" → length = 2

Deletions = 4 - 2 = 2
Insertions = 3 - 2 = 1

---

🔹 Code (C++)

int lcs(string s1, string s2) {
    int n = s1.size(), m = s2.size();

    vector<int> prev(m+1, 0), curr(m+1, 0);

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(s1[i-1] == s2[j-1])
                curr[j] = 1 + prev[j-1];
            else
                curr[j] = max(prev[j], curr[j-1]);
        }
        prev = curr;
    }

    return prev[m];
}

pair<int,int> minInsertDelete(string s1, string s2) {
    int n = s1.size(), m = s2.size();

    int L = lcs(s1, s2);

    int deletions = n - L;
    int insertions = m - L;

    return {deletions, insertions};
}

---

🔹 Total Operations

If asked:

Minimum operations = deletions + insertions
                  = n + m - 2*LCS

---

🔹 Important Variants

✅ Only deletions:

n - LCS

✅ Only insertions:

m - LCS

---

🔥 Interview Pattern

👉 If you see:

• “Convert string A → B”
• “Insert/Delete operations only”

➡️ Think:

Use LCS

---

⚡ Quick Summary

L = LCS(s1, s2)

Delete = n - L
Insert = m - L
Total = n + m - 2L

---

🧠 Intuition Shortcut

Keep common part (LCS)
Remove rest from s1
Add rest from s2

---

If you want next 🚀
I can show:
✅ Edit Distance (insert + delete + replace)
✅ Print actual operations
✅ Hard problems based on this

Just tell me 👍