Minimum Deletions & Insertions to Transform a String into another

The minimum number of edits to turn s1 into s2, when only delete and insert are allowed (no substitution), is fixed by how many characters the two strings already share in relative order: every character not in that shared subsequence must be deleted from s1, and every character of s2 not in it must be inserted — so the answer reduces entirely to finding the Longest Common Subsequence (LCS).

Recognize the pattern

• Two strings, comparing by subsequence (order preserved, not contiguous) rather than substring.
• Allowed operations are only insert/delete (no replace) — a tell that the cost model collapses to a single LCS computation instead of full 3-operation edit distance.
• Phrases like "minimum ops to make two strings identical" or "delete characters from both to make them equal" (a close cousin) also route through LCS.

Brute force → optimal

Brute force: enumerate all subsequences of s1 (2^m) and check which is also a subsequence of s2, tracking the longest. Cost: exponential time, O(m) space per candidate.

Optimal: classic 2D DP for LCS in O(m·n) time. Once LCS length L is known: deletions = m − L, insertions = n − L.

Why the formula works

The LCS is the largest set of characters from s1 you can keep untouched (in order) while still matching part of s2 in order. Every character of s1 outside that kept set is surplus → delete it (m − L deletions). Every character of s2 outside the matched set is missing from what remains → insert it (n − L insertions). No smaller edit count is possible: any valid transformation implicitly preserves some common subsequence of the untouched characters, and LCS is the largest such subsequence, so m−L and n−L are minimal by definition of L.

Complexity, derived

Let m = |s1|, n = |s2|. Build table dp[i][j] = LCS length of s1[0..i) and s2[0..j). Each of the (m+1)(n+1) cells does O(1) work (one comparison + one max), so total time is O(m·n). The table itself needs O(m·n) space, but since each row only depends on the previous row, it can be rolled down to two 1-D arrays of length n+1, giving O(min(m,n)) space if you orient the shorter string along the row. The Java below keeps the full 2-D table for clarity; a second, space-optimized version follows it and is the one to reach for at large m,n.

Worked example

s1 = "abdca" (m=5), s2 = "cbda" (n=4). Running the LCS DP end to end gives dp[5][4] = 3, and backtracking that table (move diagonally on a match, otherwise step toward the larger neighbor) fixes the exact alignment: s1[1]='b' with s2[1]='b', s1[2]='d' with s2[2]='d', and s1[4]='a' with s2[3]='a'. That pins down s1[0]='a' and s1[3]='c' as the two characters the backtrace does not touch.

Matches the stated output: 2 deletions, 1 insertion.

Java — LCS-based edit count (O(m·n) time, O(m·n) space)

class Solution {
    public int[] minDeletionInsertion(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        int lcs = dp[m][n];
        return new int[] { m - lcs, n - lcs }; // {deletions, insertions}
    }
}

Java — space-optimized (O(m·n) time, O(min(m,n)) space)

class Solution {
    public int[] minDeletionInsertion(String s1, String s2) {
        // orient the shorter string along the row to minimize memory
        if (s1.length() < s2.length()) { String t = s1; s1 = s2; s2 = t; }
        int m = s1.length(), n = s2.length();
        int[] prev = new int[n + 1];
        int[] curr = new int[n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                curr[j] = (s1.charAt(i - 1) == s2.charAt(j - 1))
                    ? prev[j - 1] + 1
                    : Math.max(prev[j], curr[j - 1]);
            }
            int[] tmp = prev; prev = curr; curr = tmp;
        }
        int lcs = prev[n];
        return new int[] { m - lcs, n - lcs }; // {deletions, insertions}
    }
}

Pitfalls

• Confusing this with full Levenshtein edit distance (which allows substitution) — that gives a different, generally smaller, op count because one substitution can replace a delete+insert pair.
• Off-by-one errors in the dp indices — dp[i][j] refers to prefixes of length i and j, not indices i and j.
• Forgetting that LCS is not unique as a subsequence, but its length is — the deletion/insertion count only needs the length, not the actual subsequence, unless you must also print which characters to touch (in which case a specific backtrace, like the one in the worked example, fixes exactly which characters move).
• Reaching for the O(m·n)-space 2-D table by default even at large m,n — swap in the rolling two-array version above once memory matters.

When to use / when not

Use this LCS-difference approach whenever operations are restricted to insert+delete only. If substitutions are also allowed and cost the same as one delete+insert, switch to full edit distance (Levenshtein) DP, which has its own recurrence (min of insert/delete/replace) and can yield a smaller answer for the same pair of strings. If you only need the LCS length itself (not the edit count), plain LCS DP suffices without the final subtraction step. For very long strings where only the length is needed and characters are few, consider Hunt–Szymanski or bitset-based LCS for sub-O(mn) speedups.

Takeaways

• Insert+delete-only transformation cost = (m − LCS) + (n − LCS); it is purely a function of LCS length.
• Derive the formula from first principles: kept characters are the LCS, everything else on each side is surplus (delete) or missing (insert).
• Distinguish this from full edit distance, which additionally allows substitution and can produce a lower cost.

Recall: Why does the minimum number of deletions plus insertions equal exactly m + n − 2·LCS(s1, s2)?

Pattern derived from classic LCS theory (Cormen et al., Introduction to Algorithms) and standard interview-prep treatments of the insert/delete-only edit distance variant.