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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Levenshtein Distance Calculation

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

DSA Typescript

function levenshtein(a: string, b: string): number {
  const dp: number[][] = [];
  for (let i = 0; i <= a.length; i++) {
    dp[i] = [];
    dp[i][0] = i;
  }
  for (let j = 0; j <= b.length; j++) {
    dp[0][j] = j;
  }
  for (let i = 1; i <= a.length; i++) {
    for (let j = 1; j <= b.length; j++) {
      if (a[i - 1] === b[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1);
      }
    }
  }
  return dp[a.length][b.length];
}

console.log(levenshtein("kitten", "sitting"));

A 3

B 4

C 2

D 5

💡 Hint

Think about 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 Matrix Initialization

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

A They are placeholders and do not affect the final result.

B They store the maximum possible edit distance between the two strings.

C They represent the cost of converting an empty string to the other string by insertions or deletions.

D They represent the number of substitutions needed to match the strings.

💡 Hint

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

The first row and column represent the cost of converting an empty string to a substring by only insertions or deletions, so they are initialized incrementally.

🔧 Debug

advanced

Identify the Error in Levenshtein Distance Implementation

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

DSA Typescript

function levenshtein(a: string, b: string): number {
  const dp: number[][] = [];
  for (let i = 0; i < a.length; i++) {
    dp[i] = [];
    dp[i][0] = i;
  }
  for (let j = 0; j <= b.length; j++) {
    dp[0][j] = j;
  }
  for (let i = 1; i <= a.length; i++) {
    for (let j = 1; j <= b.length; j++) {
      if (a[i - 1] === b[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1);
      }
    }
  }
  return dp[a.length][b.length];
}

console.log(levenshtein("abc", "yabd"));

A TypeError: Cannot set property '0' of undefined

B SyntaxError due to missing semicolon

C Returns incorrect distance value 2

D Returns correct distance value 3

💡 Hint

Check how the dp array is initialized for the first row and column.

The loop initializing dp for rows uses i < a.length, so dp[a.length] is undefined when accessed later, causing a TypeError when setting dp[a.length][j].

🚀 Application

advanced

Minimum Edit Operations to Convert Strings

Given the strings 'intention' and 'execution', what is the minimum number of edit operations (insertions, deletions, substitutions) needed to convert one into the other?

A 4

B 6

C 7

D 5

💡 Hint

Try to count the edits step-by-step or use the Levenshtein distance logic.

The Levenshtein distance between 'intention' and 'execution' is 5, representing the minimum edits needed.

🧠 Conceptual

expert

Time Complexity of Levenshtein Distance Algorithm

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

A O(2^(m + n))

B O(m * n)

C O(m^2 + n^2)

D O(m + n)

💡 Hint

Consider the size of the matrix filled during the algorithm.

The algorithm fills a matrix of size m by n, performing constant work per cell, resulting in O(m * n) time complexity.

Practice

1. What does the Levenshtein edit distance between two strings measure?

easy

A. The maximum length of common substring between two strings

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

C. The minimum number of single-character edits to change one string into the other

D. The total length of both strings combined

Solution

1. Step 1: Understand the definition of Levenshtein distance

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

2. Step 2: Compare with other options

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

3. Final Answer:

   The minimum number of single-character edits to change one string into the other -> Option C

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, not insertions/deletions
• Assuming it measures similarity score instead of edit count

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

easy

A. function levenshtein(s1: string, s2: string): number

B. function levenshtein(s1: number, s2: number): string

C. function levenshtein(s1: string[], s2: string[]): boolean

D. function levenshtein(s1: any, s2: any): void

Solution

1. Step 1: Identify correct parameter and return types

   Levenshtein distance takes two strings and returns a number representing the edit distance.

2. Step 2: Check each option's signature

   function levenshtein(s1: string, s2: string): number matches the expected input and output types. Others mismatch types or return void.

3. Final Answer:

   function levenshtein(s1: string, s2: string): number -> Option A

4. Quick Check:

   Input strings, output number [OK]

Hint: Input strings, output number for edit distance [OK]

Common Mistakes:

• Using wrong parameter types like arrays or numbers
• Returning wrong types like boolean or void
• Using any type without specifying string inputs

3. What is the output of the following TypeScript code snippet?

function levenshtein(s1: string, s2: string): number {
  const dp: number[][] = [];
  for (let i = 0; i <= s1.length; i++) {
    dp[i] = [i];
  }
  for (let j = 0; j <= s2.length; j++) {
    dp[0][j] = j;
  }
  for (let i = 1; i <= s1.length; i++) {
    for (let j = 1; j <= s2.length; j++) {
      if (s1[i - 1] === s2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1;
      }
    }
  }
  return dp[s1.length][s2.length];
}

console.log(levenshtein('kitten', 'sitting'))

medium

A. 3

B. 4

C. 5

D. 6

Solution

1. Step 1: Initialize DP table for 'kitten' and 'sitting'

   DP table rows = 7, columns = 8. Base cases set for empty prefixes.

2. Step 2: Fill DP table comparing characters and calculating minimum edits

   Calculations show minimum edits needed to convert 'kitten' to 'sitting' is 3 (substitute 'k'->'s', 'e'->'i', insert 'g').

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Levenshtein('kitten', 'sitting') = 3 [OK]

Hint: Trace DP table for small strings to find edit count [OK]

Common Mistakes:

• Counting only substitutions, ignoring insertions/deletions
• Off-by-one errors in indexing strings
• Misreading the DP initialization steps

4. Identify the bug in this TypeScript implementation of Levenshtein distance:

function levenshtein(s1: string, s2: string): number {
  const dp: number[][] = [];
  for (let i = 0; i < s1.length; i++) {
    dp[i] = [i];
  }
  for (let j = 0; j < s2.length; j++) {
    dp[0][j] = j;
  }
  for (let i = 1; i <= s1.length; i++) {
    for (let j = 1; j <= s2.length; j++) {
      if (s1[i - 1] === s2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1;
      }
    }
  }
  return dp[s1.length][s2.length];
}

medium

A. The function should return dp[0][0] instead of dp[s1.length][s2.length]

B. The dp array should be initialized with zeros instead of indices

C. The comparison should be s1[i] === s2[j], not s1[i - 1] === s2[j - 1]

D. The loops initializing dp should run up to <= length, not < length

Solution

1. Step 1: Check dp initialization loops

   Loops run from 0 to less than length, but dp needs size length+1 to include empty prefix cases.

2. Step 2: Correct loop ranges to include dp[s1.length] and dp[s2.length]

   Change loops to run up to <= length to properly initialize dp edges.

3. Final Answer:

   The loops initializing dp should run up to <= length, not < length -> Option D

4. Quick Check:

   DP size must cover full string lengths [OK]

Hint: Initialize DP arrays with length+1 for empty string cases [OK]

Common Mistakes:

• Using < length instead of <= length in loops
• Incorrect string index comparisons causing off-by-one errors
• Returning wrong dp cell ignoring full string lengths

5. Given two strings s1 = 'intention' and s2 = 'execution', what is the minimum edit distance using Levenshtein algorithm? Also, explain why this distance is correct.

hard

A. 6

B. 5

C. 4

D. 7

Solution

1. Step 1: Analyze transformations from 'intention' to 'execution'

   Operations include substituting 'i'->'e', 'n'->'x', deleting 't', substituting 'n'->'c', substituting 't'->'u'. Counting these gives 5 edits.

2. Step 2: Confirm minimal edits with DP approach

   DP table confirms minimum edits needed is 5, as fewer edits cannot convert all differing characters.

3. Final Answer:

   5 -> Option B

4. Quick Check:

   Minimum edits = 5 for 'intention' to 'execution' [OK]

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

Common Mistakes:

• Underestimating edits by ignoring deletions
• Counting only substitutions
• Misaligning characters causing wrong counts