Edit Distance
Hard About 35 min Free, no account needed
Fewest single-character edits turning one word into another.
The brief
Given two strings a and b, return the minimum number of single-character
operations (insert, delete, replace) converting a into b.
The obvious approach recurses on the three operations directly, 3^n in the worst case. The hidden test is a short adversarial pair whose longest common substring is a single character, so the recursion never gets to slide along a run of matches - it branches three ways at nearly every position and does not finish. You need to avoid recomputing the same subproblem repeatedly; an O(n * m) solution clears the bar with room to spare.
Starter code
using System;
public class Solution
{
// TODO: return the minimum insert/delete/replace operations converting a into b.
public int MinDistance(string a, string b)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- Dynamic programming
- Define subproblems and a recurrence, then reuse solved subproblems instead of recomputing them.
Related katas
- Weighted Reservation Schedule Hard Free Choose a maximum-value set of nonoverlapping reservations with a mandatory cleanup gap.
- Coin Change (Fewest Coins) Medium Free The fewest coins that make the amount, or -1.
- Coin Change II (Count the Ways) Medium Free How many coin combinations make the amount?
- Decode Ways Medium Free How many letter strings could this digit string encode?