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 the following C code that calculates the Levenshtein distance between two strings?

DSA C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int min(int a, int b, int c) {
    int m = a < b ? a : b;
    return m < c ? m : c;
}

int levenshtein(const char *s1, const char *s2) {
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    int *dp = malloc((len1 + 1) * (len2 + 1) * sizeof(int));
    for (int i = 0; i <= len1; i++) {
        for (int j = 0; j <= len2; j++) {
            if (i == 0) dp[j] = j;
            else if (j == 0) dp[i * (len2 + 1)] = i;
            else {
                int cost = (s1[i - 1] == s2[j - 1]) ? 0 : 1;
                int deletion = dp[(i - 1) * (len2 + 1) + j] + 1;
                int insertion = dp[i * (len2 + 1) + j - 1] + 1;
                int substitution = dp[(i - 1) * (len2 + 1) + j - 1] + cost;
                dp[i * (len2 + 1) + j] = min(deletion, insertion, substitution);
            }
        }
    }
    int result = dp[len1 * (len2 + 1) + len2];
    free(dp);
    return result;
}

int main() {
    printf("%d\n", levenshtein("kitten", "sitting"));
    return 0;
}

A 3

B 4

C 2

D 5

💡 Hint

Recall the minimum number of edits (insertions, deletions, substitutions) to convert 'kitten' to 'sitting'.

The Levenshtein distance between 'kitten' and 'sitting' is 3:

• Substitute 'k' with 's'
• Substitute 'e' with 'i'
• Insert 'g' at the end

🧠 Conceptual

intermediate

Understanding Levenshtein Distance Operations

Which of the following operations are considered in the Levenshtein distance calculation?

A Insertion, Swap, Transposition

B Insertion, Deletion, Substitution

C Substitution, Transposition, Swap

D Insertion, Deletion, Transposition

💡 Hint

Think about the basic edit operations allowed to transform one string into another.

Levenshtein distance counts the minimum number of insertions, deletions, and substitutions needed to change one string into another. Transposition is not included.

❓ Predict Output

advanced

Result of Levenshtein Distance with Empty String

What is the output of this C code snippet calculating the Levenshtein distance between an empty string and "abc"?

DSA C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int min(int a, int b, int c) {
    int m = a < b ? a : b;
    return m < c ? m : c;
}

int levenshtein(const char *s1, const char *s2) {
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    int *dp = malloc((len1 + 1) * (len2 + 1) * sizeof(int));
    for (int i = 0; i <= len1; i++) {
        for (int j = 0; j <= len2; j++) {
            if (i == 0) dp[j] = j;
            else if (j == 0) dp[i * (len2 + 1)] = i;
            else {
                int cost = (s1[i - 1] == s2[j - 1]) ? 0 : 1;
                int deletion = dp[(i - 1) * (len2 + 1) + j] + 1;
                int insertion = dp[i * (len2 + 1) + j - 1] + 1;
                int substitution = dp[(i - 1) * (len2 + 1) + j - 1] + cost;
                dp[i * (len2 + 1) + j] = min(deletion, insertion, substitution);
            }
        }
    }
    int result = dp[len1 * (len2 + 1) + len2];
    free(dp);
    return result;
}

int main() {
    printf("%d\n", levenshtein("", "abc"));
    return 0;
}

A 0

B 1

C 3

D 2

💡 Hint

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

To convert an empty string to "abc", we need 3 insertions, so the distance is 3.

🔧 Debug

advanced

Identify the Bug in Levenshtein Distance Code

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

DSA C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int min(int a, int b, int c) {
    int m = a < b ? a : b;
    return m < c ? m : c;
}

int levenshtein(const char *s1, const char *s2) {
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    int *dp = malloc((len1 + 1) * (len2 + 1) * sizeof(int));
    for (int i = 0; i <= len1; i++) {
        for (int j = 0; j <= len2; j++) {
            if (i == 0) dp[j] = j;
            else if (j == 0) dp[i * (len2 + 1)] = i;
            else {
                int cost = (s1[i - 1] == s2[j - 1]) ? 0 : 1;
                int deletion = dp[(i - 1) * (len2 + 1) + j] + 1;
                int insertion = dp[i * (len2 + 1) + j - 1] + 1;
                int substitution = dp[(i - 1) * (len2 + 1) + j - 1] + cost;
                dp[i * (len2 + 1) + j] = min(deletion, insertion, substitution);
            }
        }
    }
    int result = dp[len1 * (len2 + 1) + len2];
    free(dp);
    return result;
}

int main() {
    printf("%d\n", levenshtein("abc", "yabd"));
    return 0;
}

A Infinite loop in nested for loops

B Correct output 2

C Compilation error due to missing header

D Segmentation fault due to incorrect dp indexing

💡 Hint

Check how dp array is accessed when i or j is zero.

The code incorrectly assigns dp[i * (len2 + 1)] = i when j == 0, but does not assign dp[i * (len2 + 1) + j] properly for all j when i == 0. This causes inconsistent dp initialization and may lead to segmentation fault.

🧠 Conceptual

expert

Time Complexity of Levenshtein Distance Algorithm

What is the time complexity of the classic dynamic programming algorithm to compute the Levenshtein distance between two strings of lengths m and n?

A O(m * n)

B O(m + n)

C O(2^(m+n))

D O(m^2 + n^2)

💡 Hint

Consider the size of the DP table and how many cells are computed.

The algorithm fills a table of size (m+1) x (n+1), computing each cell in constant time, resulting in O(m * n) time complexity.

Practice

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

easy

A. The minimum number of insertions, deletions, or substitutions to convert one string into another

B. The number of matching characters in the same positions

C. The length difference between two strings

D. The maximum number of characters that differ between two strings

Solution

1. Step 1: Understand the definition of Edit Distance

   Edit Distance counts the smallest number of changes needed to turn one string into another.

2. Step 2: Identify allowed operations

   These operations include insertion, deletion, and substitution of characters.

3. Final Answer:

   The minimum number of insertions, deletions, or substitutions to convert one string into another -> Option A

4. Quick Check:

   Edit Distance = minimum edits needed [OK]

Hint: Think of edits needed to match strings exactly [OK]

Common Mistakes:

• Confusing edit distance with matching characters count
• Thinking it only counts substitutions
• Assuming it measures length difference only

2. Which of the following is the correct way to initialize the first row of the DP table for Levenshtein distance in C?

easy

A. for (int j = 0; j <= n; j++) dp[0][j] = j;

B. for (int i = 0; i <= m; i++) dp[i][0] = i;

C. for (int j = 1; j <= n; j++) dp[0][j] = 0;

D. for (int i = 1; i <= m; i++) dp[0][i] = i;

Solution

1. Step 1: Identify the DP table dimensions

   The DP table has dimensions (m+1) x (n+1), where m and n are string lengths.

2. Step 2: Initialize first row correctly

   The first row dp[0][j] represents converting empty string to prefix of second string, so dp[0][j] = j.

3. Final Answer:

   for (int j = 0; j <= n; j++) dp[0][j] = j; -> Option A

4. Quick Check:

   First row = 0 to n [OK]

Hint: First row = indices of second string length [OK]

Common Mistakes:

• Mixing row and column indices
• Starting loop from 1 instead of 0
• Initializing first column instead of first row

3. What is the output of the following C code snippet computing Levenshtein distance between "kitten" and "sitting"?

int min(int a, int b, int c) {
    int m = a < b ? a : b;
    return m < c ? m : c;
}

int levenshtein(char *s, char *t) {
    int m = strlen(s), n = strlen(t);
    int dp[m+1][n+1];
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            int cost = (s[i-1] == t[j-1]) ? 0 : 1;
            dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + cost);
        }
    }
    return dp[m][n];
}

printf("%d", levenshtein("kitten", "sitting"));

medium

A. 3

B. 4

C. 5

D. 6

Solution

1. Step 1: Understand the strings and operations

   "kitten" to "sitting" requires substitutions and insertions: k->s, e->i, add g.

2. Step 2: Calculate minimum edits

   Minimum edits are 3 substitutions and 1 insertion = 4 total edits.

3. Final Answer:

   4 -> Option B

4. Quick Check:

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

Hint: Recall classic example: kitten -> sitting = 4 edits [OK]

Common Mistakes:

• Counting only substitutions, missing insertions
• Confusing character positions
• Off-by-one errors in indexing

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

int levenshtein(char *s, char *t) {
    int m = strlen(s), n = strlen(t);
    int dp[m][n];
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            int cost = (s[i-1] == t[j-1]) ? 0 : 1;
            dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + cost);
        }
    }
    return dp[m][n];
}

medium

A. Loops should start from 0, not 1

B. The cost calculation is incorrect

C. dp array size should be (m+1) x (n+1), not m x n

D. Return statement should be dp[m-1][n-1]

Solution

1. Step 1: Check dp array declaration

   dp is declared as dp[m][n], but indices go up to m and n inclusive, so size is insufficient.

2. Step 2: Understand indexing needs

   We need dp of size (m+1) x (n+1) to store base cases and full computation.

3. Final Answer:

   dp array size should be (m+1) x (n+1), not m x n -> Option C

4. Quick Check:

   dp size = (m+1)*(n+1) [OK]

Hint: DP table size must cover all indices including zero [OK]

Common Mistakes:

• Declaring dp too small causing out-of-bounds errors
• Misunderstanding loop ranges
• Incorrect return index

5. Given two strings "intention" and "execution", what is the minimum edit distance using Levenshtein algorithm? Consider insertions, deletions, and substitutions only.

hard

A. 7

B. 8

C. 5

D. 6

Solution

1. Step 1: Analyze string lengths and differences

   "intention" and "execution" differ in several characters and positions.

2. Step 2: Calculate minimum edits stepwise

   Edits include substitutions (i->e, n->x, t->e, e->c, n->u, etc.) totaling 6 changes.

3. Final Answer:

   6 -> Option D

4. Quick Check:

   Levenshtein("intention", "execution") = 6 [OK]

Hint: Count substitutions and insertions carefully [OK]

Common Mistakes:

• Underestimating substitutions needed
• Ignoring insertions or deletions
• Confusing similar characters as matches