1079.js

/** ------------------------------------------------------------------------------
 * 
 * 1079. Letter Tile Possibilities
 * Topics: Backtracking
 * https://leetcode.com/problems/letter-tile-possibilities/description/?envType=daily-question&envId=2025-02-17
 * 
 ------------------------------------------------------------------------------ */
/**
 * @param {string} tiles
 * @return {number}
 */
var numTilePossibilities = function (tiles) {
  const map = new Map()

  for (let char of tiles) {
    map.set(char, (map.get(char) || 0) + 1)
  }

  return backtrack(map)
}

function backtrack(map) {
  let count = 0

  for (let [char, freq] of map.entries()) {
    if (freq === 0) continue

    map.set(char, freq - 1)
    count += 1 + backtrack(map)
    map.set(char, freq)
  }

  return count
}

var numTilePossibilities = function (tiles) {
  let result = 0
  const tileArr = tiles.split("").sort() // Sort to handle duplicates
  const used = Array(tileArr.length).fill(false)

  function backtrack() {
    for (let i = 0; i < tileArr.length; i++) {
      if (used[i]) continue // Skip already used tiles

      // Skip duplicate tiles at the same recursion level
      if (i > 0 && tileArr[i] === tileArr[i - 1] && !used[i - 1]) {
        continue
      }

      // Include the current tile
      used[i] = true
      result++ // Count this sequence as valid

      // Recurse with the current tile included
      backtrack()

      // Backtrack
      used[i] = false
    }
  }

  backtrack()
  return result
}

console.log(numTilePossibilities("AAB"))