Letter Tile Possibilities - Solution & Explanation

Problem Overview: You are given a set of letter tiles where each tile has a character printed on it. The task is to count how many distinct non‑empty sequences you can form using those tiles. Each tile can be used at most once per sequence, and sequences with the same letters but different orders count as different results.

Approach 1: Backtracking with Set (O(n! * n) time, O(n! * n) space)

This approach explicitly generates every possible sequence using backtracking. Start with an empty path and recursively append unused characters. At each step, mark a tile as used, append it to the current sequence, and explore deeper. Because duplicate characters may exist (e.g., "AAB"), store generated sequences in a set to avoid counting duplicates. Each recursive call inserts the current string into the set and continues exploring longer permutations. The algorithm essentially enumerates permutations of all possible lengths from 1 to n. Worst‑case time complexity is O(n! * n) because building and storing strings costs O(n), and the number of permutations grows factorially. Space complexity is also O(n! * n) due to storing all unique sequences.

Approach 2: DFS with Frequency Map (O(n! * n) time, O(n) space)

A more efficient strategy avoids generating duplicate sequences by tracking character counts with a frequency map. Build a map using a hash table where each character stores how many tiles remain. Then perform DFS: iterate through each character whose count is greater than zero, place it into the sequence, decrement its count, and recurse. Every time you choose a character, you increment the total number of valid sequences. After recursion, restore the count (classic backtracking step). Because the algorithm works directly on character frequencies, it never generates duplicate permutations even when tiles repeat. This dramatically reduces unnecessary work compared to storing strings in a set. Time complexity remains O(n! * n) in the worst case due to permutation growth, but practical performance is significantly better. Space complexity is O(n) for recursion depth and the frequency structure.

Both methods rely on recursive enumeration of sequences derived from a string. The key difference is whether duplicates are filtered afterward with a set or prevented during generation using frequency counts.

Recommended for interviews: DFS with a frequency map is the approach most interviewers expect. It demonstrates understanding of permutation generation, pruning duplicate work, and efficient counting. Implementing the set‑based backtracking first can help you reason about the search space, but the frequency‑map DFS shows stronger algorithmic optimization and cleaner space usage.