1079. Letter Tile Possibilities

Description

You have n  tiles, where each tile has one letter tiles[i] printed on it.

Return the number of possible non-empty sequences of letters you can make using the letters printed on those tiles.

 

Example 1:

Input: tiles = "AAB"
Output: 8
Explanation: The possible sequences are "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA".

Example 2:

Input: tiles = "AAABBC"
Output: 188

Example 3:

Input: tiles = "V"
Output: 1

 

Constraints:

• 1 <= tiles.length <= 7
• tiles consists of uppercase English letters.

 

Solutions

Solution: Backtracking

• Time complexity: O(n!)
• Space complexity: O(26 -> 1)

 

JavaScript

/**
 * @param {string} tiles
 * @return {number}
 */
const numTilePossibilities = function (tiles) {
  const BASE_CODE = 'A'.charCodeAt(0);
  const n = tiles.length;
  const letters = Array.from({ length: 26 }, () => 0);

  for (const letter of tiles) {
    const code = letter.charCodeAt(0) - BASE_CODE;

    letters[code] += 1;
  }

  const getPossibilities = () => {
    let result = 0;

    for (let code = 0; code < 26; code++) {
      if (!letters[code]) continue;

      letters[code] -= 1;
      result += 1 + getPossibilities();
      letters[code] += 1;
    }

    return result;
  };

  return getPossibilities();
};