Edit Distance Problem Levenshtein in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Levenshtein Distance Calculation

What is the output of the following Java code that calculates the Levenshtein distance between two strings?

DSA Java

public class Levenshtein {
    public static int levenshteinDistance(String s1, String s2) {
        int len1 = s1.length();
        int len2 = s2.length();
        int[][] dp = new int[len1 + 1][len2 + 1];

        for (int i = 0; i <= len1; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= len2; j++) {
            dp[0][j] = j;
        }

        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = 1 + Math.min(dp[i - 1][j - 1],
                                    Math.min(dp[i - 1][j], dp[i][j - 1]));
                }
            }
        }
        return dp[len1][len2];
    }

    public static void main(String[] args) {
        System.out.println(levenshteinDistance("kitten", "sitting"));
    }
}

A 5

B 4

C 6

D 3

💡 Hint

Count the minimum edits (insert, delete, replace) to convert 'kitten' to 'sitting'.

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

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

🧠 Conceptual

intermediate

Understanding Levenshtein Distance Operations

Which of the following operations are considered when calculating the Levenshtein distance between two strings?

A Replacement, Swapping adjacent characters, Transposition

B Insertion, Deletion, Replacement

C Insertion, Transposition, Deletion

D Insertion, Deletion, Swapping adjacent characters

💡 Hint

Think about basic edits to transform one string into another.

Levenshtein distance counts the minimum number of insertions, deletions, and replacements needed to convert one string into another. Swapping or transposition is not included.

🔧 Debug

advanced

Identify the Bug in Levenshtein Distance Code

What error will the following Java code produce when calculating Levenshtein distance?

DSA Java

public static int levenshteinDistance(String s1, String s2) {
    int len1 = s1.length();
    int len2 = s2.length();
    int[][] dp = new int[len1][len2];

    for (int i = 0; i <= len1; i++) {
        dp[i][0] = i;
    }
    for (int j = 0; j <= len2; j++) {
        dp[0][j] = j;
    }

    for (int i = 1; i <= len1; i++) {
        for (int j = 1; j <= len2; j++) {
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + Math.min(dp[i - 1][j - 1],
                                Math.min(dp[i - 1][j], dp[i][j - 1]));
            }
        }
    }
    return dp[len1][len2];
}

A No error, returns correct distance

B NullPointerException

C ArrayIndexOutOfBoundsException

D Compilation error due to missing return statement

💡 Hint

Check the size of the dp array and the indices used.

The dp array is declared with size [len1][len2], but the code accesses dp[len1][...] and dp[...][len2], which are out of bounds. The array should be sized [len1+1][len2+1].

❓ Predict Output

advanced

Levenshtein Distance for Empty String Input

What is the output of this Java code when one input string is empty?

DSA Java

public class Levenshtein {
    public static int levenshteinDistance(String s1, String s2) {
        int len1 = s1.length();
        int len2 = s2.length();
        int[][] dp = new int[len1 + 1][len2 + 1];

        for (int i = 0; i <= len1; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= len2; j++) {
            dp[0][j] = j;
        }

        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = 1 + Math.min(dp[i - 1][j - 1],
                                    Math.min(dp[i - 1][j], dp[i][j - 1]));
                }
            }
        }
        return dp[len1][len2];
    }

    public static void main(String[] args) {
        System.out.println(levenshteinDistance("", "abc"));
    }
}

A 3

B 0

C 1

D Throws StringIndexOutOfBoundsException

💡 Hint

Distance equals length of the non-empty string when the other is empty.

When one string is empty, the distance is the length of the other string because all characters must be inserted or deleted.

🧠 Conceptual

expert

Time Complexity of Levenshtein Distance Algorithm

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

A O(m * n)

B O(2^(m + n))

C O(m^2 + n^2)

D O(m + n)

💡 Hint

Consider the size of the dp table and how many cells are filled.

The algorithm fills a 2D table of size (m+1) x (n+1), so the time complexity is O(m * n).

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 characters that are the same in both strings

C. The length difference between two strings

D. The maximum number of matching characters in order

Solution

1. Step 1: Understand the definition of Edit Distance

   Edit Distance counts how many changes are needed to turn one string into another using insert, delete, or substitute operations.

2. Step 2: Compare options with definition

   Only The minimum number of insertions, deletions, or substitutions to convert one string into another correctly describes the minimum number of these operations needed.

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 [OK]

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

Common Mistakes:

• Confusing edit distance with common substring length
• Thinking it measures only character matches
• Assuming it counts only insertions or deletions

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

easy

A. public boolean levenshteinDistance(String s1, String s2)

B. public void levenshteinDistance(String s1, String s2)

C. public String levenshteinDistance(String s1, String s2)

D. public int levenshteinDistance(String s1, String s2)

Solution

1. Step 1: Identify the return type for Levenshtein distance

   The Levenshtein distance is a number representing the count of edits, so the return type should be int.

2. Step 2: Check method signature correctness

   public int levenshteinDistance(String s1, String s2) returns int and takes two String parameters, which is correct. Other options return void, String, or boolean, which are incorrect for this purpose.

3. Final Answer:

   public int levenshteinDistance(String s1, String s2) -> Option D

4. Quick Check:

   Return type int for distance [OK]

Hint: Distance is a number, so return int [OK]

Common Mistakes:

• Using void return type and not returning a value
• Returning String instead of int
• Returning boolean which is not suitable

3. What is the Levenshtein distance between the strings "kitten" and "sitting"?

medium

A. 2

B. 3

C. 4

D. 5

Solution

1. Step 1: Compare strings and count edits

   Transform "kitten" to "sitting": substitute 'k'->'s', substitute 'e'->'i', insert 'g' at end. Total edits = 3.

2. Step 2: Confirm minimal edits

   No fewer than 3 edits can convert "kitten" to "sitting".

3. Final Answer:

   3 -> Option B

4. Quick Check:

   kitten -> sitting needs 3 edits [OK]

Hint: Count substitutions, insertions, deletions carefully [OK]

Common Mistakes:

• Counting only substitutions and missing insertions
• Miscounting edits by skipping characters
• Assuming length difference equals distance

4. Given the following Java code snippet to compute Levenshtein distance, what is the error?

public int levenshteinDistance(String s1, String s2) {
  int[][] dp = new int[s1.length()][s2.length()];
  for (int i = 0; i <= s1.length(); i++) {
    for (int j = 0; j <= s2.length(); j++) {
      if (i == 0) dp[i][j] = j;
      else if (j == 0) dp[i][j] = i;
      else if (s1.charAt(i - 1) == s2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1];
      else dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j]));
    }
  }
  return dp[s1.length()][s2.length()];
}

medium

A. The return statement should return dp[s1.length()-1][s2.length()-1]

B. The loops should start from 1 instead of 0

C. Array dp is declared with wrong size causing IndexOutOfBoundsException

D. The character comparison uses wrong indices

Solution

1. Step 1: Check dp array size

   dp is declared as new int[s1.length()][s2.length()] but loops run up to s1.length() and s2.length() inclusive, causing index out of bounds.

2. Step 2: Identify correct dp size

   dp should be new int[s1.length()+1][s2.length()+1] to accommodate indices up to s1.length() and s2.length().

3. Final Answer:

   Array dp is declared with wrong size causing IndexOutOfBoundsException -> Option C

4. Quick Check:

   dp size must be length+1 [OK]

Hint: dp array size must be lengths + 1 [OK]

Common Mistakes:

• Declaring dp with exact string lengths only
• Returning dp at wrong indices
• Starting loops incorrectly causing errors

5. What is the Levenshtein distance between the strings "intention" and "execution"?

hard

A. 6

B. 5

C. 4

D. 7

Solution

1. Step 1: Align the strings and identify differences

   Both strings have length 9. The minimal edit sequence includes substitutions and insertions/deletions. The Levenshtein distance is 6, as confirmed by standard DP computation.

2. Step 2: Confirm no better alignment

   Insertions/deletions and substitutions combined yield a minimum of 6 edits.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   intention -> execution = 6 [OK]

Hint: Align strings and compute minimum operations via mismatches or DP trace [OK]

Common Mistakes:

• Counting 6 by proposing unnecessary insert/delete
• Underestimating by ignoring all mismatches (e.g., 4)
• Overestimating due to poor alignment