Problem Statement & Formal Constraints

You have n tiles, where each tile has one uppercase English 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.

Mathematical Combinatorics vs. Backtracking DFS

A naive approach might generate all possible permutations using a boolean used array, storing each string in a std::set<string> to eliminate duplicate sequences. However, because duplicates occur due to repeated tiles (e.g. two 'A' tiles), generating duplicate permutations and discarding them in a hash set wastes significant CPU cycles and triggers excessive dynamic memory allocations.

Instead, we model the sequence generation as a Depth-First Search on a Character Frequency Map. When we choose a character to place at the current position, choosing any instance of that identical letter produces isomorphic search subtrees. Therefore, by grouping identical characters into a frequency counter, we only branch once per unique available character at each tree level.

Approach 1: Frequency Array DFS (Optimal C++)

Because letters are restricted to uppercase English letters ('A' through 'Z'), we replace hash tables with a fixed-size 26-element array allocated entirely on the CPU stack:

#include <string>
#include <vector>
#include <numeric>

class Solution {
public:
    int numTilePossibilities(std::string tiles) {
        // Frequency array for 26 uppercase English characters
        int count[26] = {0};
        for (char c : tiles) {
            count[c - 'A']++;
        }
        return dfs(count);
    }

private:
    int dfs(int count[26]) {
        int totalSequences = 0;

        for (int i = 0; i < 26; ++i) {
            if (count[i] == 0) continue;

            // 1. Choose letter: each valid choice creates 1 new non-empty sequence
            totalSequences++;
            count[i]--;

            // 2. Recurse down the search tree
            totalSequences += dfs(count);

            // 3. Backtrack: restore count for other branches
            count[i]++;
        }

        return totalSequences;
    }
};

Approach 2: High-Performance TypeScript Implementation

In TypeScript, we allocate an Int32Array(26) to avoid garbage collector overhead and ensure continuous typed-array memory representation in V8:

/**
 * Calculates the number of non-empty letter sequences possible from given tiles.
 * Time Complexity: O(Unique Permutations)
 * Space Complexity: O(N) call stack depth
 */
export function numTilePossibilities(tiles: string): number {
  const count = new Int32Array(26);
  const codeA = 'A'.charCodeAt(0);

  for (let i = 0; i < tiles.length; i++) {
    count[tiles.charCodeAt(i) - codeA]++;
  }

  function dfs(): number {
    let sequences = 0;
    for (let i = 0; i < 26; i++) {
      if (count[i] === 0) continue;

      sequences++;
      count[i]--;
      sequences += dfs();
      count[i]++;
    }
    return sequences;
  }

  return dfs();
}

Complexity Analysis (Time & Space)

The table below compares algorithmic implementations for LeetCode 1079:

Real-World Full-Stack Engineering Applications

Combinatorial frequency-map backtracking architectures power several mission-critical production systems:

• Combinatorial Testing Matrix Generators: In automated software QA, generating valid feature flag permutations where multiple flags share identical behavior mirrors frequency-based tile generation.
• Lexical Anagram & Scrabble Engines: High-throughput word gaming servers pre-filter dictionary AST tries by tracking remaining tile counts rather than testing every permutation.
• Query Token Expansion in Search Engines: Expanding multi-token search queries with synonym substitution matrices to compute permutation relevance rankings.

Frequently Asked Questions

Why does the DFS call increment totalSequences by 1 on each valid choice?

Because any non-empty prefix generated at the current recursion node represents a unique valid sequence. Unlike standard permutation problems that only count leaves of length $N$, LeetCode 1079 requires counting sequences of all lengths $1 le k le N$.

Why is a fixed 26-element array faster than an unordered_map?

An array access count[c - 'A'] compiles directly to single-cycle indexed memory addressing without hashing overhead, cache-line misses, or pointer chasing associated with node-based hash tables.

Can this problem be solved without recursion using generating functions?

Yes. Using exponential generating functions (EGF) and multinomial coefficients, one can compute polynomial expansions to obtain exact sequence counts mathematically, though for $N le 7$, frequency DFS is faster to execute and simpler to maintain.

How does the call stack depth scale with tile length?

The maximum recursion depth is strictly bounded by $N$ (the total number of tiles), which is at most 7. The call stack consumes less than a single kilobyte of memory.

Conclusion & Performance Takeaways

LeetCode 1079 illustrates how restructuring the search space—transitioning from string-based permutation generation to character-frequency DFS—eliminates redundant computation. For constrained alphabets, static typed arrays provide maximum execution speed with minimal garbage collector pressure.