The challenge

Given a lowercase word, return every permutation of its letters in alphabetical order. Do not use built-in permutation libraries.

Examples:

permutations('the');
// → ['eht', 'eth', 'het', 'hte', 'teh', 'the']

permutations('a');
// → ['a']

This is a Codewars classic in the JavaScript track. The two stumbling blocks are generating the permutations from scratch and producing them alphabetically.

Solution 1: recursion + dedup + sort

The most direct version. Recurse to build, Set to dedupe, sort to order:

function permutations(s) {
  if (s.length === 1) return [s];

  const result = [];
  for (let i = 0; i < s.length; i++) {
    const ch = s[i];
    const rest = s.slice(0, i) + s.slice(i + 1);
    for (const sub of permutations(rest)) {
      result.push(ch + sub);
    }
  }
  return [...new Set(result)].sort();
}

Why this works:

  1. Base case. A one-character string has only itself as a permutation.
  2. Recursive case. Pick each character once, remove it from the string, recurse on the rest, then prepend the picked character to each sub-result.
  3. Dedup. new Set(result) removes duplicates — important for words like 'hello' with repeated letters.
  4. Sort. .sort() without a compare function sorts strings lexicographically, which equals alphabetical order for lowercase letters.

Solution 2: backtracking with sorted input

This version produces permutations already in alphabetical order — no final sort needed:

function permutations(s) {
  const chars = [...s].sort(); // sorted input → sorted output
  const result = [];

  const backtrack = (path, remaining) => {
    if (remaining.length === 0) {
      result.push(path);
      return;
    }
    const seen = new Set();
    for (let i = 0; i < remaining.length; i++) {
      const ch = remaining[i];
      if (seen.has(ch)) continue; // skip duplicate at this level
      seen.add(ch);
      backtrack(path + ch, remaining.slice(0, i).concat(remaining.slice(i + 1)));
    }
  };

  backtrack('', chars);
  return result;
}

Why this works: Because the input characters are sorted, the for-loop tries them in alphabetical order at every recursion level. The seen set at each level prevents duplicate permutations from repeated letters. Result: the array fills alphabetically without a final sort.

Solution 3: iterative next-permutation

Generates each permutation in lexicographic order using the algorithm std::next_permutation uses in C++:

function permutations(s) {
  const arr = [...s].sort();
  const result = [arr.join('')];

  const nextPermutation = (a) => {
    let i = a.length - 2;
    while (i >= 0 && a[i] >= a[i + 1]) i--;
    if (i < 0) return false;
    let j = a.length - 1;
    while (a[j] <= a[i]) j--;
    [a[i], a[j]] = [a[j], a[i]];
    // reverse a[i+1..end]
    for (let l = i + 1, r = a.length - 1; l < r; l++, r--) {
      [a[l], a[r]] = [a[r], a[l]];
    }
    return true;
  };

  while (nextPermutation(arr)) {
    result.push(arr.join(''));
  }
  return result;
}

Why this works: nextPermutation mutates the array to its next lexicographic state. Starting from the sorted array (the smallest permutation), repeatedly calling it walks through every arrangement in order until it returns false. Skips duplicates naturally because it only emits each lexicographic state once.

Complexity

Solution Time Space
Recursion + Set + sort O(n! × n log n) O(n! × n)
Backtracking O(n! × n) O(n! × n)
next-permutation O(n! × n) O(n! × n)

n! is the number of permutations, n is the per-string cost. For n = 10 that is 3.6 million strings — keep input short.

Test cases

console.assert(JSON.stringify(permutations('a')) === '["a"]');
console.assert(JSON.stringify(permutations('ab')) === '["ab","ba"]');
console.assert(permutations('abc').length === 6);
console.assert(JSON.stringify(permutations('the')) ===
               '["eht","eth","het","hte","teh","the"]');
console.assert(permutations('hello').length === 60); // 5!/2! = 60 unique