Edit Distance Problem Levenshtein in DSA Java - Time & Space Complexity

Time Complexity: Edit Distance Problem Levenshtein

O(m x n)

Understanding Time Complexity

We want to understand how the time needed to find the edit distance between two words grows as the words get longer.

The question is: how does the number of steps change when the input words increase in length?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public int levenshtein(String s1, String s2) {
    int m = s1.length();
    int n = s2.length();
    int[][] dp = new int[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++) {
            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[m][n];
}
    

This code calculates the minimum number of edits (insert, delete, replace) to change one word into another using a table.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops filling a 2D table of size m by n.
• How many times: The inner loop runs n times for each of the m iterations of the outer loop, so about m x n times.

How Execution Grows With Input

As the lengths of the two words grow, the number of steps grows roughly by multiplying their lengths.

Input Size (m, n)	Approx. Operations
10, 10	100
100, 100	10,000
1000, 1000	1,000,000

Pattern observation: Doubling the length of both words roughly quadruples the work because the table size grows with the product of lengths.

Final Time Complexity

Time Complexity: O(m x n)

This means the time needed grows proportionally to the product of the lengths of the two words.

Common Mistake

[X] Wrong: "The algorithm runs in linear time because it just compares characters one by one."

[OK] Correct: The algorithm compares all pairs of characters in a table, not just one by one, so it takes time proportional to both word lengths multiplied.

Interview Connect

Understanding this time complexity helps you explain how dynamic programming solves problems efficiently by breaking them into smaller parts.

Self-Check

"What if we used recursion without memoization? How would the time complexity change?"

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