Letter Tile Possibilities

medium backtracking counting dfs

Problem

You have a set of 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.

Inputtiles = "AAB"

Output8

The sequences are "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA".

tiles (letters)

def num_tile_possibilities(tiles):
    count = [0] * 26
    for c in tiles:
        count[ord(c) - ord('A')] += 1

    def dfs():
        total = 0
        for i in range(26):
            if count[i] > 0:
                total += 1          # use this tile as next letter
                count[i] -= 1
                total += dfs()      # extend the sequence
                count[i] += 1       # backtrack
        return total

    return dfs()

function numTilePossibilities(tiles) {
  const count = new Array(26).fill(0);
  for (const c of tiles) count[c.charCodeAt(0) - 65]++;

  function dfs() {
    let total = 0;
    for (let i = 0; i < 26; i++) {
      if (count[i] > 0) {
        total += 1;          // use this tile as next letter
        count[i]--;
        total += dfs();      // extend the sequence
        count[i]++;          // backtrack
      }
    }
    return total;
  }

  return dfs();
}

class Solution {
    int[] count = new int[26];

    public int numTilePossibilities(String tiles) {
        for (char c : tiles.toCharArray()) count[c - 'A']++;
        return dfs();
    }

    private int dfs() {
        int total = 0;
        for (int i = 0; i < 26; i++) {
            if (count[i] > 0) {
                total += 1;          // use this tile as next letter
                count[i]--;
                total += dfs();      // extend the sequence
                count[i]++;          // backtrack
            }
        }
        return total;
    }
}

class Solution {
public:
    int count[26] = {0};

    int numTilePossibilities(string tiles) {
        for (char c : tiles) count[c - 'A']++;
        return dfs();
    }

    int dfs() {
        int total = 0;
        for (int i = 0; i < 26; i++) {
            if (count[i] > 0) {
                total += 1;          // use this tile as next letter
                count[i]--;
                total += dfs();      // extend the sequence
                count[i]++;          // backtrack
            }
        }
        return total;
    }
};

Explanation

We need to count every non-empty sequence we can spell from the tiles. Instead of generating the actual strings, we count them as we build them, which is much simpler and faster.

First we make a frequency count: count[i] is how many tiles of letter i we have left. This lets us treat identical tiles as the same choice, which automatically avoids counting duplicate sequences.

The recursive dfs() tries to add one more letter to the current sequence. For each letter that still has tiles available, it does three things: count this new sequence (total += 1), use up a tile (count[i] -= 1), recurse to extend further, then backtrack by putting the tile back (count[i] += 1).

Example: tiles = "AAB" gives count with A=2, B=1. Picking A counts "A", then from there A gives "AA", B gives "AB", and so on. Every distinct extension adds one to the total.

Because each recursive call counts itself the moment it places a letter, the grand total is exactly the number of valid non-empty sequences.

Time: O(n · n!) Space: O(n)