Skip to main content

Minimum Edit Operations Between Strings

hard
Dynamic ProgrammingStringDp 2d
Asked atGoogleAmazonMicrosoftMetaBloombergApple

Problem Description

Given two strings `source` and `target`, return the **minimum number of single-character operations** required to transform `source` into `target`.

The three permitted operations are:
1. **Insert** a character at any position.
2. **Delete** a character at any position.
3. **Replace** a character at any position with another character.

This is the classic **Levenshtein edit distance**.

**Example 1:**
```
Input: source = "kitten", target = "sitting"
Output: 3
Explanation:
kitten → sitten (replace 'k' with 's')
sitten → sittin (replace 'e' with 'i')
sittin → sitting (insert 'g')
```

**Example 2:**
```
Input: source = "cloud", target = "aloud"
Output: 2
Explanation:
cloud → cloud (insert 'a') → aloud (delete 'c') OR cloud → aloud (replace 'c' with 'a', delete nothing). Actually: replace 'c'→'a' = 1, then done? No — 'aloud' vs 'cloud': replace c→a (1), and l stays, o stays, u stays, d stays. Wait: cloud(5) vs aloud(5): c→a (replace), l=l, o=o, u=u, d=d. Answer is 1... Let me recount.
Actually: source="cloud" target="aloud": c→a replace(1 op), rest match. Answer = 1.
```

**Example 2 (corrected):**
```
Input: source = "cloud", target = "proud"
Output: 2
Explanation:
cloud → cloud — replace c→p (1), l→l, o→r? No.
c-l-o-u-d vs p-r-o-u-d: replace c→p (1), replace l→r (2), rest match. Answer = 2.
```

Constraints

  • 0 <= source.length <= 500
  • 0 <= target.length <= 500
  • source and target consist of lowercase English letters.

Follow-up

Extend the solution to also **reconstruct the sequence of operations** (insertions, deletions, replacements) that achieves the minimum edit distance.

Hints

Try the problem first. If you get stuck, you can reveal hints one at a time.

Solution

Leaderboard

No entries yet for python.

Be the first — submit an accepted solution.