Skip to content
Katabench
Try free

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 performance bar

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

C#
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.

C# coding challenges →

What it practices

Dynamic programming
Define subproblems and a recurrence, then reuse solved subproblems instead of recomputing them.

Related katas