Edit Distance Problem Levenshtein in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Levenshtein Distance Calculation

What is the output of this C# code that calculates the Levenshtein distance between "kitten" and "sitting"?

DSA C#

using System;

class Program {
    static int LevenshteinDistance(string s, string t) {
        int n = s.Length;
        int m = t.Length;
        int[,] d = new int[n + 1, m + 1];

        for (int i = 0; i <= n; i++) d[i, 0] = i;
        for (int j = 0; j <= m; j++) d[0, j] = j;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                int cost = (s[i - 1] == t[j - 1]) ? 0 : 1;
                d[i, j] = Math.Min(Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1), d[i - 1, j - 1] + cost);
            }
        }
        return d[n, m];
    }

    static void Main() {
        Console.WriteLine(LevenshteinDistance("kitten", "sitting"));
    }
}

A 3

B 5

C 4

D 6

💡 Hint

Count the minimum edits (insertions, deletions, substitutions) to convert "kitten" to "sitting".

The Levenshtein distance between "kitten" and "sitting" is 3. The edits are: substitute 'k' with 's', substitute 'e' with 'i', insert 'g' at the end.

🧠 Conceptual

intermediate

Understanding Levenshtein Distance Matrix Initialization

In the Levenshtein distance algorithm, why do we initialize the first row and first column of the matrix with incremental values?

A To optimize the algorithm by skipping unnecessary calculations.

B To store the ASCII values of characters for comparison.

C To mark visited cells in the matrix during recursion.

D To represent the cost of converting an empty string to prefixes of the other string by insertions or deletions.

💡 Hint

Think about how many edits it takes to convert an empty string to a string of length n.

The first row and column represent the cost of converting an empty string to prefixes of the other string, which requires insertions or deletions equal to the prefix length.

🔧 Debug

advanced

Identify the Bug in Levenshtein Distance Implementation

What error will this C# code produce when calculating the Levenshtein distance between "abc" and "yabd"?

DSA C#

using System;

class Program {
    static int LevenshteinDistance(string s, string t) {
        int n = s.Length;
        int m = t.Length;
        int[,] d = new int[n + 1, m + 1];

        for (int i = 0; i <= n; i++) d[i, 0] = i;
        for (int j = 0; j <= m; j++) d[0, j] = j;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                int cost = (s[i - 1] == t[j - 1]) ? 0 : 1;
                d[i, j] = Math.Min(Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1), d[i - 1, j - 1] + cost);
            }
        }
        return d[n, m];
    }

    static void Main() {
        Console.WriteLine(LevenshteinDistance("abc", "yabd"));
    }
}

A IndexOutOfRangeException

B NullReferenceException

C No error, correct output

D Returns incorrect distance value

💡 Hint

Check the size of the matrix and the loop boundaries carefully.

The matrix is declared with size [n, m], but loops run up to n and m inclusive, causing index out of range errors when accessing d[i, j].

🚀 Application

advanced

Minimum Edit Operations to Convert Strings

Given the strings "flaw" and "lawn", what is the minimum number of edit operations (insertions, deletions, substitutions) needed to convert "flaw" into "lawn"?

A 4

B 3

C 2

D 1

💡 Hint

Try to align the characters and count the minimum edits.

The minimum edits are 2: delete 'f' and insert 'n' at the end.

❓ Predict Output

expert

Output of Levenshtein Distance with Empty String

What is the output of this C# code that calculates the Levenshtein distance between an empty string and "algorithm"?

DSA C#

using System;

class Program {
    static int LevenshteinDistance(string s, string t) {
        int n = s.Length;
        int m = t.Length;
        int[,] d = new int[n + 1, m + 1];

        for (int i = 0; i <= n; i++) d[i, 0] = i;
        for (int j = 0; j <= m; j++) d[0, j] = j;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                int cost = (s[i - 1] == t[j - 1]) ? 0 : 1;
                d[i, j] = Math.Min(Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1), d[i - 1, j - 1] + cost);
            }
        }
        return d[n, m];
    }

    static void Main() {
        Console.WriteLine(LevenshteinDistance("", "algorithm"));
    }
}

A 8

B 9

C 0

D 1

💡 Hint

Consider how many insertions are needed to convert an empty string to "algorithm".

Since the first string is empty, the distance equals the length of the second string, which is 9.

Practice

1. What does the Levenshtein Edit Distance between two strings measure?

easy

A. The total length of both strings combined

B. The maximum length of common substring between two strings

C. The number of characters that are the same in both strings

D. The minimum number of single-character edits to change one string into another

Solution

1. Step 1: Understand the definition of Levenshtein distance

   It counts the minimum edits (insertions, deletions, substitutions) to convert one string into another.

2. Step 2: Compare with other options

   Options B and C describe different string metrics, not edit distance.

3. Final Answer:

   The minimum number of single-character edits to change one string into another -> Option D

4. Quick Check:

   Edit distance = minimum edits [OK]

Hint: Edit distance counts minimal edits to match strings [OK]

Common Mistakes:

• Confusing edit distance with longest common substring
• Thinking it counts only substitutions
• Assuming it measures string length

2. Which of the following C# method signatures correctly represents a function to compute Levenshtein distance between two strings s1 and s2?

easy

A. private string LevenshteinDistance(string s1, string s2)

B. public void LevenshteinDistance(int s1, int s2)

C. public int LevenshteinDistance(string s1, string s2)

D. public int LevenshteinDistance(int[] s1, int[] s2)

Solution

1. Step 1: Check parameter types for string inputs

   The function should accept two strings, so parameters must be string types.

2. Step 2: Check return type for distance value

   Distance is an integer, so return type should be int, not void or string.

3. Final Answer:

   public int LevenshteinDistance(string s1, string s2) -> Option C

4. Quick Check:

   Function signature matches string inputs and int output [OK]

Hint: Function takes strings, returns int distance [OK]

Common Mistakes:

• Using void return type instead of int
• Using int parameters instead of strings
• Returning string instead of int

3. What is the output of the following C# code snippet?

var s1 = "kitten";
var s2 = "sitting";
Console.WriteLine(LevenshteinDistance(s1, s2));

int LevenshteinDistance(string a, string b) {
    int[,] dp = new int[a.Length + 1, b.Length + 1];
    for (int i = 0; i <= a.Length; i++) dp[i, 0] = i;
    for (int j = 0; j <= b.Length; j++) dp[0, j] = j;
    for (int i = 1; i <= a.Length; i++) {
        for (int j = 1; j <= b.Length; j++) {
            int cost = (a[i - 1] == b[j - 1]) ? 0 : 1;
            dp[i, j] = Math.Min(Math.Min(dp[i - 1, j] + 1, dp[i, j - 1] + 1), dp[i - 1, j - 1] + cost);
        }
    }
    return dp[a.Length, b.Length];
}

medium

A. 3

B. 4

C. 5

D. 6

Solution

1. Step 1: Understand the strings and operations

   "kitten" to "sitting" requires substitutions, insertions, deletions.

2. Step 2: Calculate Levenshtein distance manually

   Changes: k->s (substitution), e->i (substitution), t->t (no change), t->t (no change), e->i (substitution), n->n (no change), add g (insertion) = 3 substitutions + 1 insertion = 4 edits total.

3. Final Answer:

   4 -> Option B

4. Quick Check:

   Distance("kitten", "sitting") = 4 [OK]

Hint: Remember common example: kitten -> sitting = 4 edits [OK]

Common Mistakes:

• Counting only substitutions, ignoring insertions
• Miscounting character positions
• Confusing with Hamming distance

4. Identify the bug in this Levenshtein distance C# code snippet:

int LevenshteinDistance(string a, string b) {
    int[,] dp = new int[a.Length, b.Length];
    for (int i = 0; i < a.Length; i++) dp[i, 0] = i;
    for (int j = 0; j < b.Length; j++) dp[0, j] = j;
    for (int i = 1; i < a.Length; i++) {
        for (int j = 1; j < b.Length; j++) {
            int cost = (a[i] == b[j]) ? 0 : 1;
            dp[i, j] = Math.Min(Math.Min(dp[i - 1, j] + 1, dp[i, j - 1] + 1), dp[i - 1, j - 1] + cost);
        }
    }
    return dp[a.Length - 1, b.Length - 1];
}

medium

A. Array size should be (a.Length+1, b.Length+1) and loops adjusted

B. Cost calculation should use a[i-1] and b[j-1]

C. Return statement should be dp[a.Length, b.Length]

D. No bug, code is correct

Solution

1. Step 1: Check array size and indexing

   dp array must be sized (a.Length+1, b.Length+1) to include empty prefixes; current size misses last row/column.

2. Step 2: Adjust loops to run from 0 to length inclusive

   Loops should run to <= length to fill dp correctly; current loops miss last indices.

3. Final Answer:

   Array size should be (a.Length+1, b.Length+1) and loops adjusted -> Option A

4. Quick Check:

   dp array size must include empty string row/column [OK]

Hint: dp array must be one larger than string lengths [OK]

Common Mistakes:

• Using array size equal to string length only
• Incorrect loop bounds causing index errors
• Ignoring empty string base cases

5. Given two strings s1 = "intention" and s2 = "execution", what is the Levenshtein distance between them? Use the standard operations: insert, delete, substitute.

hard

A. 5

B. 6

C. 4

D. 7

Solution

1. Step 1: Analyze differences between "intention" and "execution"

   Compare characters and count minimal edits: substitutions and insertions/deletions.

2. Step 2: Calculate minimal edits manually

   Edits: i->e (substitution), n->x (substitution), t->c (substitution), insert u, substitute n->o, substitute n->n (no change), total 5 edits.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   Distance("intention", "execution") = 5 [OK]

Hint: Count substitutions and insertions carefully [OK]

Common Mistakes:

• Underestimating substitutions needed
• Ignoring insertions or deletions
• Confusing with Hamming distance