Minimum Insertions / Deletions to Convert String

Medium20–25 min

Topics

Dynamic ProgrammingString

Companies

AmazonMicrosoftFlipkart

Given two strings `s1` and `s2`, find the minimum combined number of character insertions into `s1` and deletions from `s1` needed to turn `s1` into `s2`. The characters that make up the longest common subsequence of `s1` and `s2` never need to be touched — they're already sitting in the right relative order in both strings, so they can act as a fixed skeleton. Everything else has to change: a character of `s1` that isn't part of that shared skeleton has no partner in `s2` and must be deleted, and a character of `s2` that isn't part of it has no partner in `s1` yet and must be inserted. That turns the whole problem into computing one number — the length of the longest common subsequence — and plugging it into a simple formula.

Test Case 1:

Input:s1 = "heap", s2 = "pea"

Output:3

Explanation:"ea" is the longest stretch common to both, kept in place. "h" and "p" get deleted from "heap" (2 deletions), and "p" gets inserted to finish spelling "pea" (1 insertion) — 3 operations total.

Test Case 2:

Input:s1 = "abc", s2 = "abc"

Output:0

Explanation:The strings already match — nothing to insert or delete.

Test Case 3:

Input:s1 = "abc", s2 = "def"

Output:6

Explanation:Not a single letter is shared, so every character of both strings has to go — delete all 3 of "abc" and insert all 3 of "def".

Constraints

◆0 ≤ s1.length, s2.length ≤ 12
◆s1 and s2 consist of lowercase English letters

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Recursive Longest Common Subsequence

Brute

Whatever the longest common subsequence of s1 and s2 turns out to be, it never needs to move — it's already sitting in the right relative order in both strings. Every character of s1 outside that shared subsequence has no counterpart, so it must be deleted; every character of s2 outside it has nothing to line up with in s1, so it must be inserted. That means the total operations needed is just (s1's length − LCS length) + (s2's length − LCS length). Finding the LCS length recursively is the classic two-pointer walk from the ends of both strings: if the trailing characters match, both belong to the subsequence and the search shrinks by one on each side; otherwise try dropping the trailing character of either string and keep the better result. Without caching, the same (i, j) pair gets resolved from scratch through every path that reaches it, so the work doubles with each extra character.

TimeO(2ⁿ⁺ᵐ)

SpaceO(n + m)

Java

Try it out

class Solution {
    private String s1, s2;
    public int minOperations(String s1, String s2) {
        this.s1 = s1;
        this.s2 = s2;
        int lcs = solve(s1.length(), s2.length());
        return (s1.length() - lcs) + (s2.length() - lcs);
    }
    private int solve(int i, int j) {
        if (i == 0 || j == 0) return 0;
        if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
            return 1 + solve(i - 1, j - 1);
        }
        return Math.max(solve(i - 1, j), solve(i, j - 1));
    }
}

Optimal — Bottom-Up LCS Table

Optimal

Build the LCS length table bottom-up instead of re-deriving each (i, j) pair from scratch. dp[i][j] holds the LCS length between the first i characters of s1 and the first j characters of s2. Row 0 and column 0 stay 0 (an empty prefix shares nothing). Filling left to right, top to bottom: if the current characters match, dp[i][j] is one more than the diagonal neighbor dp[i-1][j-1]; otherwise it's the better of dropping the current character of s1 (dp[i-1][j]) or of s2 (dp[i][j-1]), both already computed. Once dp[n][m] holds the full LCS length, the same delete/insert formula from the brute force gives the answer directly.

TimeO(n·m)

SpaceO(n·m)