// levenshtein.js
function levenshtein(a, b) {
    // Make a the shorter string to minimize space usage
    if (a.length > b.length) {
        [a, b] = [b, a];
    }

    const m = a.length;
    const n = b.length;

    // Two rows for DP
    let prev = Array.from({ length: m + 1 }, (_, i) => i);
    let curr = new Array(m + 1);

    for (let j = 1; j <= n; j++) {
        curr[0] = j;
        for (let i = 1; i <= m; i++) {
            const cost = a[i - 1] === b[j - 1] ? 0 : 1;
            curr[i] = Math.min(
                prev[i] + 1,        // deletion
                curr[i - 1] + 1,    // insertion
                prev[i - 1] + cost  // substitution
            );
        }
        // Swap rows
        [prev, curr] = [curr, prev];
    }

    return prev[m];
}

module.exports = levenshtein;

// levenshtein.test.js
const assert = require('assert');
const levenshtein = require('./levenshtein');

// Identical strings
assert.strictEqual(levenshtein('abc', 'abc'), 0);

// One empty string
assert.strictEqual(levenshtein('', 'abc'), 3);
assert.strictEqual(levenshtein('abc', ''), 3);

// Both empty
assert.strictEqual(levenshtein('', ''), 0);

// Single-character difference (substitution)
assert.strictEqual(levenshtein('a', 'b'), 1);
assert.strictEqual(levenshtein('a', 'a'), 0);

// Insertions
assert.strictEqual(levenshtein('ab', 'abc'), 1);
assert.strictEqual(levenshtein('abc', 'ab'), 1);

// Deletions
assert.strictEqual(levenshtein('abc', 'ac'), 1);

// Substitutions
assert.strictEqual(levenshtein('cat', 'bat'), 1);

// Longer realistic case (kitten -> sitting should be 3)
assert.strictEqual(levenshtein('kitten', 'sitting'), 3);

// Additional case
assert.strictEqual(levenshtein('flaw', 'lawn'), 2);

console.log('All tests passed.');

Complexity analysis:

• Time: O(m·n) where m and n are the lengths of the two strings.
• Space: O(min(m, n)) – only two rows of length min(m, n) + 1 are maintained.

Levenshtein Distance Implementation

levenshtein.js

/**
 * Calculates the Levenshtein distance between two strings.
 * @param {string} a - First string
 * @param {string} b - Second string
 * @returns {number} The minimum number of single-character edits required
 */
function levenshtein(a, b) {
  // Handle empty strings
  if (a.length === 0) return b.length;
  if (b.length === 0) return a.length;

  // Ensure a is the shorter string for space efficiency
  if (a.length > b.length) {
    [a, b] = [b, a];
  }

  const lenA = a.length;
  const lenB = b.length;

  // Use two rows instead of full matrix for O(min(m,n)) space
  let prevRow = Array.from({ length: lenA + 1 }, (_, i) => i);
  let currRow = new Array(lenA + 1);

  for (let j = 1; j <= lenB; j++) {
    currRow[0] = j;

    for (let i = 1; i <= lenA; i++) {
      const cost = a[i - 1] === b[j - 1] ? 0 : 1;

      currRow[i] = Math.min(
        prevRow[i] + 1,      // deletion
        currRow[i - 1] + 1,  // insertion
        prevRow[i - 1] + cost // substitution
      );
    }

    // Swap rows
    [prevRow, currRow] = [currRow, prevRow];
  }

  return prevRow[lenA];
}

module.exports = levenshtein;

levenshtein.test.js

const assert = require('assert');
const levenshtein = require('./levenshtein');

console.log('Running Levenshtein distance tests...\n');

// Test 1: Identical strings
assert.strictEqual(levenshtein('hello', 'hello'), 0, 'Identical strings should have distance 0');
console.log('✓ Identical strings');

// Test 2: Both empty
assert.strictEqual(levenshtein('', ''), 0, 'Both empty strings should have distance 0');
console.log('✓ Both empty strings');

// Test 3: First string empty
assert.strictEqual(levenshtein('', 'abc'), 3, 'Empty first string should return length of second');
console.log('✓ First string empty');

// Test 4: Second string empty
assert.strictEqual(levenshtein('abc', ''), 3, 'Empty second string should return length of first');
console.log('✓ Second string empty');

// Test 5: Single character difference (substitution)
assert.strictEqual(levenshtein('a', 'b'), 1, 'Single character difference');
console.log('✓ Single character difference');

// Test 6: Insertions
assert.strictEqual(levenshtein('cat', 'cats'), 1, 'One insertion');
assert.strictEqual(levenshtein('a', 'abc'), 2, 'Two insertions');
console.log('✓ Insertions');

// Test 7: Deletions
assert.strictEqual(levenshtein('cats', 'cat'), 1, 'One deletion');
assert.strictEqual(levenshtein('abc', 'a'), 2, 'Two deletions');
console.log('✓ Deletions');

// Test 8: Substitutions
assert.strictEqual(levenshtein('abc', 'adc'), 1, 'One substitution');
assert.strictEqual(levenshtein('hello', 'hallo'), 1, 'One substitution (e→a)');
console.log('✓ Substitutions');

// Test 9: Classic case - "kitten" to "sitting"
// Operations: kitten → sitten (substitute k→s), sitten → sittin (substitute e→i), sittin → sitting (insert g)
assert.strictEqual(levenshtein('kitten', 'sitting'), 3, 'kitten → sitting should be 3');
console.log('✓ Classic case: kitten → sitting (distance: 3)');

// Test 10: Case sensitivity
assert.strictEqual(levenshtein('Hello', 'hello'), 1, 'Case sensitive comparison');
console.log('✓ Case sensitivity');

// Test 11: Longer strings
assert.strictEqual(levenshtein('saturday', 'sunday'), 3, 'saturday → sunday');
console.log('✓ Longer strings: saturday → sunday (distance: 3)');

// Test 12: Completely different strings
assert.strictEqual(levenshtein('abc', 'def'), 3, 'Completely different strings');
console.log('✓ Completely different strings');

// Test 13: One string is substring of another
assert.strictEqual(levenshtein('book', 'bookkeeper'), 6, 'One string is substring');
console.log('✓ One string is substring of another');

console.log('\n✅ All tests passed!');

Complexity Analysis

Key Optimizations:

1. Two-row approach: Instead of storing the entire DP table, we only keep the previous and current rows since each cell only depends on the row above and the current row.
2. String swapping: We ensure the first argument is the shorter string, minimizing space usage to O(min(m, n)).

Levenshtein Distance Implementation

Complexity:

• Time: O(m × n), where m and n are the lengths of the two strings.
• Space: O(min(m, n)) — we only keep two rows (previous and current), and we ensure the shorter string is used for the row width.

levenshtein.js

'use strict';

/**
 * Compute the Levenshtein edit distance between two strings.
 * @param {string} a
 * @param {string} b
 * @returns {number}
 */
function levenshtein(a, b) {
  if (typeof a !== 'string' || typeof b !== 'string') {
    throw new TypeError('Both arguments must be strings');
  }

  // Quick exits
  if (a === b) return 0;
  if (a.length === 0) return b.length;
  if (b.length === 0) return a.length;

  // Ensure `b` is the shorter string -> row width = min(m, n)
  if (a.length < b.length) {
    const tmp = a;
    a = b;
    b = tmp;
  }

  const m = a.length;
  const n = b.length;

  let prev = new Array(n + 1);
  let curr = new Array(n + 1);

  for (let j = 0; j <= n; j++) prev[j] = j;

  for (let i = 1; i <= m; i++) {
    curr[0] = i;
    const ac = a.charCodeAt(i - 1);

    for (let j = 1; j <= n; j++) {
      const cost = ac === b.charCodeAt(j - 1) ? 0 : 1;
      const deletion = prev[j] + 1;
      const insertion = curr[j - 1] + 1;
      const substitution = prev[j - 1] + cost;

      let min = deletion;
      if (insertion < min) min = insertion;
      if (substitution < min) min = substitution;
      curr[j] = min;
    }

    // Swap rows
    const tmp = prev;
    prev = curr;
    curr = tmp;
  }

  return prev[n];
}

module.exports = levenshtein;

levenshtein.test.js

'use strict';

const assert = require('node:assert/strict');
const levenshtein = require('./levenshtein');

// Identical strings
assert.equal(levenshtein('', ''), 0, 'both empty');
assert.equal(levenshtein('abc', 'abc'), 0, 'identical non-empty');
assert.equal(levenshtein('hello world', 'hello world'), 0, 'identical with spaces');

// One empty string
assert.equal(levenshtein('', 'abc'), 3, 'first empty');
assert.equal(levenshtein('abcdef', ''), 6, 'second empty');

// Single-character difference (substitution)
assert.equal(levenshtein('cat', 'bat'), 1, 'single substitution at start');
assert.equal(levenshtein('cat', 'car'), 1, 'single substitution at end');

// Insertions
assert.equal(levenshtein('cat', 'cats'), 1, 'single insertion at end');
assert.equal(levenshtein('cat', 'scat'), 1, 'single insertion at start');
assert.equal(levenshtein('abc', 'aXbYc'), 2, 'two insertions');

// Deletions
assert.equal(levenshtein('cats', 'cat'), 1, 'single deletion at end');
assert.equal(levenshtein('scat', 'cat'), 1, 'single deletion at start');
assert.equal(levenshtein('aXbYc', 'abc'), 2, 'two deletions');

// Pure substitutions
assert.equal(levenshtein('abc', 'xyz'), 3, 'all substitutions');

// Classic realistic cases
assert.equal(levenshtein('kitten', 'sitting'), 3, 'kitten -> sitting');
assert.equal(levenshtein('Saturday', 'Sunday'), 3, 'Saturday -> Sunday');
assert.equal(levenshtein('flaw', 'lawn'), 2, 'flaw -> lawn');
assert.equal(levenshtein('gumbo', 'gambol'), 2, 'gumbo -> gambol');

// Symmetry
assert.equal(
  levenshtein('kitten', 'sitting'),
  levenshtein('sitting', 'kitten'),
  'distance is symmetric'
);

// Case sensitivity
assert.equal(levenshtein('abc', 'ABC'), 3, 'case sensitive');

// Type validation
assert.throws(() => levenshtein(null, 'abc'), TypeError);
assert.throws(() => levenshtein('abc', 42), TypeError);

console.log('All Levenshtein tests passed.');

Run with:

node levenshtein.test.js