Solution Minimum Deletions & Insertions to Transform a String into another

Problem Statement

Given strings s1 and s2, we need to transform s1 into s2 by deleting and inserting characters. Write a function to calculate the count of the minimum number of deletion and insertion operations.

Example 1:

Input: s1 = "abc"
       s2 = "fbc"
Output: 1 deletion and 1 insertion.
Explanation: We need to delete {'a'} and insert {'f'} to s1 to transform it into s2.

Example 2:

Input: s1 = "abdca"
       s2 = "cbda"
Output: 2 deletions and 1 insertion.
Explanation: We need to delete {'a', 'c'} and insert {'c'} to s1 to transform it into s2.

Example 3:

Input: s1 = "passport"
       s2 = "ppsspt"
Output: 3 deletions and 1 insertion
Explanation: We need to delete {'a', 'o', 'r'} and insert {'p'} to s1 to transform it into s2.

Constraints:

1 <= s1.length, s2.length <= 1000`
s1 and s2 consist of only lowercase English characters.

Solution

This problem can easily be converted to the "Longest Common Subsequence" (LCS). If we can find the LCS of the two input strings, we can easily find how many characters we need to insert and delete from s1. Here is how we can do this:

Let's assume len1 is the length of s1 and len2 is the length of s2.
Now let's assume c1 is the length of LCS of the two strings s1 and s2.
To transform s1 into s2, we need to delete everything from s1 which is not part of LCS, so minimum deletions we need to perform from s1 => len1 - c1
Similarly, we need to insert everything in s1 which is present in s2 but not part of LCS, so minimum insertions we need to perform in s1 => len2 - c1

Let's jump directly to the bottom-up dynamic programming solution:

Bottom-up Dynamic Programming

Here is the code for our bottom-up dynamic programming approach:

java

class Solution {

  public List<Integer> findMDI(String s1, String s2) {
    int c1 = findLCSLength(s1, s2);
    int deletions = s1.length() - c1;
    int insertions = s2.length() - c1;
    List<Integer> result = new ArrayList<>();
    result.add(deletions);
    result.add(insertions);
    return result;
  }

  private int findLCSLength(String s1, String s2) {
    int[][] dp = new int[s1.length() + 1][s2.length() + 1];
    int maxLength = 0;
    for (int i = 1; i <= s1.length(); i++) {
      for (int j = 1; j <= s2.length(); j++) {
        if (s1.charAt(i - 1) == s2.charAt(j - 1)) dp[i][j] =
          1 + dp[i - 1][j - 1];
        else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);

        maxLength = Math.max(maxLength, dp[i][j]);
      }
    }
    return maxLength;
  }

  public static void main(String[] args) {
    Solution mdi = new Solution();
    List<Integer> res;
    res = mdi.findMDI("abc", "fbc");
    System.out.println("1 -> Number of Deletions: " + res.get(0));
    System.out.println("1 -> Number of Insertions: " + res.get(0));
    res = mdi.findMDI("abdca", "cbda");
    System.out.println("2 -> Number of Deletions: " + res.get(0));
    System.out.println("2 -> Number of Insertions: " + res.get(0));
    res = mdi.findMDI("passport", "ppsspt");
    System.out.println("3 -> Number of Deletions: " + res.get(0));
    System.out.println("3 -> Number of Insertions: " + res.get(0));
  }
}

The time and space complexity of the above algorithm is , where ‘m’ and ‘n’ are the lengths of the two input strings.

🤖 Don't fully get this? Learn it with Claude

Stuck on Solution Minimum Deletions & Insertions to Transform a String into another? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Solution Minimum Deletions & Insertions to Transform a String into another** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Solution Minimum Deletions & Insertions to Transform a String into another** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Solution Minimum Deletions & Insertions to Transform a String into another**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Solution Minimum Deletions & Insertions to Transform a String into another**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Solution Longest Common Subsequenc Solution Longest Increasing Subseq →