permutations.js

var numTilePossibilities = function(tiles) {
  return rec(tiles)
};

function rec(tiles) {
  if (tiles.length === 1) {
    return 1
  }
  
  let sum = 0
  for (let i=0; i < tiles.length; i++) {
    let result = rec(tiles.slice(0,i) + tiles.slice(i+1))
    sum += result + 1
  }
  
  return sum
}

Sabía que estaba muy cerca, la solución refactorizada es la siguiente:

var numTilePossibilities = function(tiles) {
  if (tiles.length === 1) return 1
  
  const visited = {}
  
  let sum = 0
  for (let i=0; i < tiles.length; i++) {
    let current = tiles[i]
    
    if (!visited[current]) {
      let result = numTilePossibilities(tiles.slice(0,i) + tiles.slice(i+1))
      sum += result + 1
      visited[current] = true
    }
  }
  
  return sum
};

Sólo necesitábamos ir guardando las letras y no repetir el proceso para las duplicadas!