Here are both files:

levenshtein.js

/**
 * Computes the Levenshtein (edit) distance between two strings.
 *
 * Time complexity:  O(m * n) — every cell of the virtual matrix is visited once.
 * Space complexity: O(min(m, n)) — only two rows are kept in memory at any time.
 *
 * @param {string} a
 * @param {string} b
 * @returns {number} minimum edit distance
 */
function levenshtein(a, b) {
  if (typeof a !== "string" || typeof b !== "string") {
    throw new TypeError("Both arguments must be strings");
  }

  // Ensure 'a' is the shorter string so the two arrays stay as small as possible.
  if (a.length > b.length) {
    [a, b] = [b, a];
  }

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

  // Base cases — one or both strings are empty.
  if (m === 0) return n;
  if (n === 0) return m;

  // prev[j] = distance between a[0..i-1] and b[0..j-1] (previous row)
  // curr[j] = distance being computed for the current row i
  let prev = new Array(m + 1);
  let curr = new Array(m + 1);

  // Initialise the first row: transforming "" → a[0..j-1] costs j insertions.
  for (let j = 0; j <= m; j++) {
    prev[j] = j;
  }

  for (let i = 1; i <= n; i++) {
    // Transforming a[0..i-1] → "" costs i deletions.
    curr[0] = i;

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

      curr[j] = Math.min(
        prev[j] + 1,                    // deletion  (remove b[i-1])
        curr[j - 1] + 1,                // insertion (insert a[j-1])
        prev[j - 1] + substitutionCost  // substitution / match
      );
    }

    // Swap rows — curr becomes the new prev for the next iteration.
    [prev, curr] = [curr, prev];
  }

  // After the final swap, prev holds the last completed row.
  return prev[m];
}

module.exports = { levenshtein };

levenshtein.test.js

"use strict";

const assert = require("assert");
const { levenshtein } = require("./levenshtein");

// ─── helpers ────────────────────────────────────────────────────────────────

let passed = 0;
let failed = 0;

function test(description, fn) {
  try {
    fn();
    console.log(`  ✓  ${description}`);
    passed++;
  } catch (err) {
    console.error(`  ✗  ${description}`);
    console.error(`     ${err.message}`);
    failed++;
  }
}

function assertEqual(actual, expected, hint = "") {
  assert.strictEqual(
    actual,
    expected,
    `Expected ${expected}, got ${actual}${hint ? " — " + hint : ""}`
  );
}

// ─── test suites ─────────────────────────────────────────────────────────────

console.log("\nLevenshtein distance tests\n");

// 1. Both strings identical
console.log("Identical strings");
test("empty string vs empty string → 0", () =>
  assertEqual(levenshtein("", ""), 0));
test('"abc" vs "abc" → 0', () =>
  assertEqual(levenshtein("abc", "abc"), 0));
test("single char vs itself → 0", () =>
  assertEqual(levenshtein("z", "z"), 0));

// 2. One or both strings empty
console.log("\nEmpty string edge cases");
test('"" vs "abc" → 3 (3 insertions)', () =>
  assertEqual(levenshtein("", "abc"), 3));
test('"abc" vs "" → 3 (3 deletions)', () =>
  assertEqual(levenshtein("abc", ""), 3));
test('"" vs "x" → 1', () =>
  assertEqual(levenshtein("", "x"), 1));
test('"x" vs "" → 1', () =>
  assertEqual(levenshtein("x", ""), 1));

// 3. Single-character differences
console.log("\nSingle-character differences");
test('"a" vs "b" → 1 (substitution)', () =>
  assertEqual(levenshtein("a", "b"), 1));
test('"ab" vs "a" → 1 (deletion)', () =>
  assertEqual(levenshtein("ab", "a"), 1));
test('"a" vs "ab" → 1 (insertion)', () =>
  assertEqual(levenshtein("a", "ab"), 1));

// 4. Pure insertions
console.log("\nInsertions");
test('"abc" vs "aXbYc" → 2', () =>
  assertEqual(levenshtein("abc", "aXbYc"), 2));
test('"abc" vs "xabc" → 1 (prepend)', () =>
  assertEqual(levenshtein("abc", "xabc"), 1));
test('"abc" vs "abcx" → 1 (append)', () =>
  assertEqual(levenshtein("abc", "abcx"), 1));

// 5. Pure deletions
console.log("\nDeletions");
test('"aXbYc" vs "abc" → 2', () =>
  assertEqual(levenshtein("aXbYc", "abc"), 2));
test('"xabc" vs "abc" → 1', () =>
  assertEqual(levenshtein("xabc", "abc"), 1));

// 6. Pure substitutions
console.log("\nSubstitutions");
test('"abc" vs "axc" → 1', () =>
  assertEqual(levenshtein("abc", "axc"), 1));
test('"abc" vs "xyz" → 3 (all different)', () =>
  assertEqual(levenshtein("abc", "xyz"), 3));
test('"saturday" vs "sunday" → 3', () =>
  assertEqual(levenshtein("saturday", "sunday"), 3));

// 7. Realistic longer cases
console.log("\nLonger / realistic cases");
test('"kitten" vs "sitting" → 3', () =>
  assertEqual(levenshtein("kitten", "sitting"), 3));
test('"intention" vs "execution" → 5', () =>
  assertEqual(levenshtein("intention", "execution"), 5));
test('"rosetta" vs "racecar" → 6', () =>
  assertEqual(levenshtein("rosetta", "racecar"), 6));

// 8. Symmetry property
console.log("\nSymmetry");
const pairs = [["kitten", "sitting"], ["abc", "xyz"], ["", "hello"]];
pairs.forEach(([x, y]) => {
  test(`levenshtein("${x}", "${y}") === levenshtein("${y}", "${x}")`, () =>
    assertEqual(levenshtein(x, y), levenshtein(y, x)));
});

// 9. Type guard
console.log("\nInput validation");
test("throws TypeError for non-string first argument", () =>
  assert.throws(() => levenshtein(42, "abc"), TypeError));
test("throws TypeError for non-string second argument", () =>
  assert.throws(() => levenshtein("abc", null), TypeError));

// ─── summary ─────────────────────────────────────────────────────────────────

console.log(`\n${"─".repeat(40)}`);
console.log(`Results: ${passed} passed, ${failed} failed\n`);
if (failed > 0) process.exit(1);

Complexity notes

Key design decisions

1. Row swapping — the two arrays are swapped via destructuring at the end of each outer iteration, avoiding any allocation inside the hot loop.
2. Shorter string as columns — by ensuring a is always the shorter string, the two arrays are as small as possible, which improves cache behaviour for very long strings.
3. No external dependencies — the test file uses only Node's built-in assert module and a minimal hand-rolled test() helper, so node levenshtein.test.js is all that is needed to run it.

Here are the implementations for levenshtein.js and levenshtein.test.js:

levenshtein.js

function levenshtein(a, b) {
  if (a === b) return 0;
  if (a.length === 0) return b.length;
  if (b.length === 0) return a.length;

  // Use two rows to save space
  let prevRow = Array(b.length + 1).fill(0);
  let currRow = Array(b.length + 1).fill(0);

  // Initialize first row
  for (let j = 0; j <= b.length; j++) {
    prevRow[j] = j;
  }

  for (let i = 1; i <= a.length; i++) {
    currRow[0] = i; // Cost of deleting all characters up to i

    for (let j = 1; j <= b.length; j++) {
      const deletionCost = prevRow[j] + 1;
      const insertionCost = currRow[j - 1] + 1;
      const substitutionCost = prevRow[j - 1] + (a[i - 1] === b[j - 1] ? 0 : 1);

      currRow[j] = Math.min(deletionCost, insertionCost, substitutionCost);
    }

    // Swap rows for next iteration
    [prevRow, currRow] = [currRow, prevRow];
    currRow.fill(0); // Reset current row
  }

  return prevRow[b.length];
}

module.exports = levenshtein;

levenshtein.test.js

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

assert.strictEqual(levenshtein('kitten', 'sitting'), 3);
assert.strictEqual(levenshtein('hello', 'hello'), 0);
assert.strictEqual(levenshtein('', 'abc'), 3);
assert.strictEqual(levenshtein('abc', ''), 3);
assert.strictEqual(levenshtein('', ''), 0);
assert.strictEqual(levenshtein('a', 'b'), 1);
assert.strictEqual(levenshtein('abc', 'ab'), 1); // deletion
assert.strictEqual(levenshtein('ab', 'abc'), 1); // insertion
assert.strictEqual(levenshtein('abc', 'adc'), 1); // substitution
assert.strictEqual(levenshtein('saturday', 'sunday'), 3);

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

Complexity Analysis:

• Time Complexity: O(m*n), where m and n are the lengths of the two strings. This is because we need to fill a matrix of size m×n (though we optimize space by using two rows).
• Space Complexity: O(min(m, n)), since we only keep two rows in memory at any time (each of length n+1). This is more space-efficient than the full O(m*n) matrix approach.

The implementation handles all edge cases (empty strings, identical strings) and uses a space-optimized approach with two rows. The test file covers all the required cases.

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 keep only two rows and ensure the shorter string indexes the row.

// levenshtein.js
'use strict';

function levenshtein(a, b) {
  if (typeof a !== 'string' || typeof b !== 'string') {
    throw new TypeError('Both arguments must be strings');
  }

  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 so the rows have length min(m, n) + 1
  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 del = prev[j] + 1;
      const ins = curr[j - 1] + 1;
      const sub = prev[j - 1] + cost;
      let min = del < ins ? del : ins;
      if (sub < min) min = sub;
      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('assert');
const levenshtein = require('./levenshtein');

// Identical strings
assert.strictEqual(levenshtein('', ''), 0, 'both empty');
assert.strictEqual(levenshtein('abc', 'abc'), 0, 'identical strings');
assert.strictEqual(levenshtein('hello world', 'hello world'), 0, 'identical with space');

// One empty string
assert.strictEqual(levenshtein('', 'abc'), 3, 'first empty');
assert.strictEqual(levenshtein('abc', ''), 3, 'second empty');
assert.strictEqual(levenshtein('', 'x'), 1, 'one empty, one char');

// Single-character difference (substitution)
assert.strictEqual(levenshtein('a', 'b'), 1, 'single char substitution');
assert.strictEqual(levenshtein('cat', 'bat'), 1, 'one substitution');
assert.strictEqual(levenshtein('cat', 'car'), 1, 'one substitution end');

// Insertions
assert.strictEqual(levenshtein('cat', 'cats'), 1, 'single insertion at end');
assert.strictEqual(levenshtein('cat', 'chat'), 1, 'single insertion in middle');
assert.strictEqual(levenshtein('abc', 'abcdef'), 3, 'multiple insertions');

// Deletions
assert.strictEqual(levenshtein('cats', 'cat'), 1, 'single deletion at end');
assert.strictEqual(levenshtein('chat', 'cat'), 1, 'single deletion in middle');
assert.strictEqual(levenshtein('abcdef', 'abc'), 3, 'multiple deletions');

// Substitutions
assert.strictEqual(levenshtein('abc', 'xyz'), 3, 'all substituted');
assert.strictEqual(levenshtein('book', 'back'), 2, 'two substitutions');

// Mixed operations (longer realistic cases)
assert.strictEqual(levenshtein('kitten', 'sitting'), 3, 'kitten -> sitting');
assert.strictEqual(levenshtein('sitting', 'kitten'), 3, 'symmetry: sitting -> kitten');
assert.strictEqual(levenshtein('Saturday', 'Sunday'), 3, 'Saturday -> Sunday');
assert.strictEqual(levenshtein('flaw', 'lawn'), 2, 'flaw -> lawn');
assert.strictEqual(levenshtein('intention', 'execution'), 5, 'intention -> execution');

// Symmetry property checks
assert.strictEqual(
  levenshtein('algorithm', 'altruistic'),
  levenshtein('altruistic', 'algorithm'),
  'symmetry property'
);

// Type checking
assert.throws(() => levenshtein(123, 'abc'), TypeError, 'throws on non-string');
assert.throws(() => levenshtein('abc', null), TypeError, 'throws on null');

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

Run with:

node levenshtein.test.js