Edit Distance Problem Levenshtein in DSA C++ - 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 minimum edits between two words grows as the words get longer.

How does the work increase when the input words become bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int editDistance(string s1, string s2) {
    int m = s1.size(), n = s2.size();
    vector> dp(m + 1, vector(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[i - 1] == s2[j - 1])
                dp[i][j] = dp[i - 1][j - 1];
            else
                dp[i][j] = 1 + min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][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: Outer loop runs m times, inner loop runs n times, so total m x n times.

How Execution Grows With Input

As the lengths of the two words increase, the number of operations grows by multiplying their sizes.

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 needed.

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 only depends on the longer word length, so it is O(max(m, n))"

[OK] Correct: The algorithm compares every character of one word with every character of the other, so both lengths matter equally.

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 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 how many changes are needed to make two strings equal.

2. Step 2: Identify allowed operations

   Allowed operations are 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
• Ignoring substitution as an allowed operation
• Thinking it measures only length difference

2. Which of the following is the correct way to initialize the base case for the DP table in Levenshtein distance calculation in C++?

easy

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

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

C. dp[0][0] = 1;

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

Solution

1. Step 1: Understand base case meaning

   dp[i][0] means converting first i characters of string1 to empty string, so requires i deletions.

2. Step 2: Identify correct initialization

   Setting dp[i][0] = i correctly counts deletions needed for empty second string.

3. Final Answer:

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

4. Quick Check:

   Base case rows = index count [OK]

Hint: Base case dp[i][0] = i for deletions [OK]

Common Mistakes:

• Initializing dp[0][j] incorrectly to zero
• Starting loops from 1 instead of 0
• Setting dp[0][0] to 1 instead of 0

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

int levenshteinDistance(const string &s, const string &t) {
    int m = s.size(), n = t.size();
    vector dp(m + 1, vector<int>(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 (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1];
            else dp[i][j] = 1 + min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]});
        }
    }
    return dp[m][n];
}

cout << levenshteinDistance("kitten", "sitting") << endl;

medium

A. 4

B. 6

C. 5

D. 3

Solution

1. Step 1: Understand the strings and operations

   "kitten" to "sitting" requires substitutions and insertions.

2. Step 2: Calculate minimum edits

   Substitute 'k'->'s', substitute 'e'->'i', insert 'g' at end, total 3 edits.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Levenshtein distance("kitten", "sitting") = 3 [OK]

Hint: Count substitutions + insertions needed [OK]

Common Mistakes:

• Counting only substitutions, ignoring insertions
• Misaligning indices causing off-by-one errors
• Confusing Levenshtein with Hamming distance

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

int levenshteinDistance(string s, string t) {
    int m = s.size(), n = t.size();
    vector dp(m, vector<int>(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++) {
            if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1];
            else dp[i][j] = 1 + min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]});
        }
    }
    return dp[m][n];
}

medium

A. The return statement should be dp[m-1][n-1]

B. The dp vector is initialized with size m x n instead of (m+1) x (n+1)

C. The loops should start from 0 instead of 1

D. The comparison s[i] == t[j] is incorrect

Solution

1. Step 1: Check dp vector initialization

   dp must have size (m+1) x (n+1) to include base cases for empty strings.

2. Step 2: Identify impact of wrong size

   With size m x n, accessing dp[m][0] or dp[0][n] causes out-of-bounds errors.

3. Final Answer:

   The dp vector is initialized with size m x n instead of (m+1) x (n+1) -> Option B

4. Quick Check:

   dp size must be (m+1) x (n+1) [OK]

Hint: dp size must cover empty string cases [OK]

Common Mistakes:

• Forgetting to add +1 to dp dimensions
• Returning dp[m][n] without proper dp size
• Incorrect loop ranges causing index errors

5. Given two strings "intention" and "execution", what is the minimum edit distance using Levenshtein algorithm? Show the reasoning for each step.

hard

A. 7

B. 5

C. 6

D. 8

Solution

1. Step 1: Analyze character differences

   Compare "intention" and "execution" character by character, counting edits needed.

2. Step 2: Calculate minimal edits

   The optimal alignment requires 6 edits: substitutions, insertions, and deletions to match exactly.

3. Final Answer:

   6 -> Option C

4. Quick Check:

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

Hint: Count substitutions and insertions carefully [OK]

Common Mistakes:

• Ignoring insertions or deletions
• Miscounting substitutions
• Assuming only substitutions needed