Code Implementation

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        from collections import Counter

        def backtrack(counter):
            total = 0
            for ch in counter:
                if counter[ch] > 0:
                    total += 1
                    counter[ch] -= 1
                    total += backtrack(counter)
                    counter[ch] += 1
            return total

        return backtrack(Counter(tiles))
      

class Solution {
public:
    int numTilePossibilities(string tiles) {
        vector count(26, 0);
        for (char c : tiles) count[c - 'A']++;
        return backtrack(count);
    }
    int backtrack(vector& count) {
        int total = 0;
        for (int i = 0; i < 26; ++i) {
            if (count[i] == 0) continue;
            total++;
            count[i]--;
            total += backtrack(count);
            count[i]++;
        }
        return total;
    }
};
      

class Solution {
    public int numTilePossibilities(String tiles) {
        int[] count = new int[26];
        for (char c : tiles.toCharArray()) count[c - 'A']++;
        return backtrack(count);
    }
    private int backtrack(int[] count) {
        int total = 0;
        for (int i = 0; i < 26; i++) {
            if (count[i] == 0) continue;
            total++;
            count[i]--;
            total += backtrack(count);
            count[i]++;
        }
        return total;
    }
}
      

var numTilePossibilities = function(tiles) {
    let count = Array(26).fill(0);
    for (let c of tiles) count[c.charCodeAt(0) - 65]++;
    function backtrack(count) {
        let total = 0;
        for (let i = 0; i < 26; i++) {
            if (count[i] === 0) continue;
            total++;
            count[i]--;
            total += backtrack(count);
            count[i]++;
        }
        return total;
    }
    return backtrack(count);
};
      

Problem Description

Given a string tiles consisting of uppercase English letters, you can use each letter tile at most once to create non-empty sequences (words). Each sequence is a permutation of some or all tiles, and sequences that differ in order or composition are considered different. Your task is to return the total number of possible non-empty sequences that can be made using the tiles.

• Each tile can be used only once per sequence.
• Sequences are counted as different if their order or letters differ.
• Input: tiles (string, 1 ≤ length ≤ 7, only 'A'-'Z')
• Output: Integer - total number of non-empty possible sequences.

Thought Process

At first glance, it seems like we need to generate all possible permutations of the tiles, for every possible sequence length from 1 up to the length of tiles. However, if there are duplicate letters, many sequences will be the same unless we carefully avoid duplicates. A brute-force approach would generate all possible arrangements, but this would be inefficient and potentially count the same sequence multiple times.

To optimize, we need a way to systematically explore all possible sequences without repeating any, even with duplicate tiles. The key insight is to use backtracking: for each step, try picking any available letter (that still has remaining unused tiles), add it to the sequence, and recursively continue. By decrementing and restoring counts as we go, we avoid using any tile more than once per sequence, and we naturally avoid duplicate sequences.

Solution Approach

The solution uses a recursive backtracking approach with a frequency counter:

1. Count Tiles: Use a frequency counter (like a hash map or array) to track how many of each letter you have. This allows us to pick only available tiles and handle duplicates efficiently.
2. Backtracking: For each recursive call:
   • Loop through all possible letters.
   • If a letter is available (count > 0), choose it:
   • Decrement its count (mark as used).
   • Count this as a valid sequence (since every choice forms a new sequence).
   • Recursively continue to add more letters.
   • After recursion, restore the count (backtrack).
   • Repeat for all available letters at this state.
3. Base Case: When no tiles are left to use, simply return 0 (no further sequences can be formed).
4. Result: The sum of all valid sequence counts from each recursive path gives the final answer. We do not need to explicitly store sequences; just count them.

This approach ensures that every possible sequence is counted exactly once, even with duplicate tiles.

Example Walkthrough

Let's consider the input tiles = "AAB".

• We start with counts: A:2, B:1.
• First, pick 'A': counts become A:1, B:1.
• Pick 'A' again: counts A:0, B:1.
• Pick 'B': counts A:0, B:0. Sequence "AAB" counted.
• Backtrack, pick 'B': counts A:1, B:0. Sequence "AB" counted.
• Backtrack to start, pick 'B': counts A:2, B:0.
• Pick 'A': counts A:1, B:0. Sequence "BA" counted.
• Pick 'A' again: counts A:0, B:0. Sequence "BAA" counted.
• All single-letter sequences ("A", "B") are also counted at each step where only one letter is picked.

All unique sequences: "A", "AA", "AAB", "AB", "ABA", "B", "BA", "BAA" (8 total).

Time and Space Complexity

Brute-force Approach: Generating all permutations of all lengths would be O(n * n!), where n is the number of tiles. This quickly becomes infeasible for larger n, especially with duplicates.

Optimized Backtracking: For each recursive call, we can branch up to 26 times (for each letter), but the actual number is much less due to limited tile counts and pruning by used tiles. The total number of sequences is bounded by the sum over all possible combinations, which is less than n! but still exponential in the worst case. However, since n ≤ 7, this is acceptable in practice.

Space Complexity: The recursion stack depth is at most n (the length of tiles), and the counter uses O(1) space (since there are only 26 letters). So space complexity is O(n).

Summary

The key to solving the Letter Tile Possibilities problem is to use backtracking with a frequency counter. This approach efficiently explores all possible sequences by picking available tiles, avoids duplicates naturally, and counts each unique sequence exactly once. The solution is elegant because it leverages recursion and counting rather than generating and storing all permutations, making it both efficient and easy to understand for small input sizes.