Domain 2MediumMEDIUM

Letter Tile Possibilities

LeetCode problem 1079: Letter Tile Possibilities (medium).

Domain: medium•Updated: 2026-09-08
#Backtracking

Problem Breakdown

We are given a string representing physical tiles with letters on them (e.g., “AAB”). We need to count how many distinct non-empty sequences can be formed using these tiles as ingredients.

Key Inputs & Outputs:

  • Input: A string tiles containing uppercase English letters. The length is small (1≤N≤71 \le N \le 7).
  • Output: An integer representing the total number of unique valid permutations (sequences) possible from any subset size kk, where 1≤k≤N1 \le k \le N.

Implicit Constraints & Nuances:

  • Limited Supply: If we have two ‘A’s, we can use one or both in a sequence, but not three. We must track the count of each character type available at every step.
  • Order Matters: “AB” is distinct from “BA”. This implies permutations, not combinations.
  • Duplicates Handling: Since tiles with identical letters are indistinguishable for forming unique sequences (e.g., picking first ‘A’ vs second ‘A’ in “AA”), we must iterate over unique character types at each recursion level to avoid redundant branches.

Intuition

If I were to try a brute-force approach, I might generate all subsets of the tiles and then permute them for every subset size. However, this is inefficient because it treats identical letters as distinct items (e.g., treating “A1” and “A2” in “AAABBC”), leading to massive overcounting (O(N!)O(N!) per subset).

Key Insight: This problem maps directly to counting permutations of a multiset. We can use Backtracking. At each step, we build the sequence one character at a time. To handle duplicates efficiently without generating duplicate branches in our recursion tree:

  1. Maintain a frequency map (count) for every unique letter available.
  2. In the recursive function, iterate only over unique characters that have count > 0.
  3. For each valid character type picked, decrement its count to simulate using it, recurse, then increment back (backtrack).

This ensures we explore exactly one branch for every unique sequence prefix without redundancy.

Approach

  1. Frequency Map: Convert the input string into a frequency map (Counter) of characters. This allows us to track available tiles efficiently (O(N)O(N) time/space setup).
  2. Recursive Function (DFS): Define backtrack() which returns an integer count of valid sequences formable from current state.
  3. Iteration: Inside the function, iterate through all unique keys in our frequency map.
  4. Branching Logic: For each character type:
    • Check if available (count > 0).
    • Decrement its count (consume tile).
    • Add 1 to result immediately? Yes. Every time we successfully pick a valid tile, it completes at least one unique sequence ending there (the current prefix). We also add the results of extending this sequence further via recursion (backtrack() call).
    • Recurse: Call backtrack().
    • Backtrack: Increment count back to restore state for other branches.
  5. Accumulate: Sum up all valid paths found across all unique character choices at each depth level and return the total.

Complexity Analysis

  • Time Complexity: O(N⋅KN)O(N \cdot K^N) where KK is alphabet size (26) or more accurately, proportional to the number of unique permutations generated by subsets. Given constraints (N≤7N \le 7), this fits easily within time limits. The recursion visits each valid sequence state exactly once in terms of logic flow relative to output count.
  • Space Complexity: O(N)O(N) for the call stack depth (max length of tiles) and O(1)O(1) auxiliary space since our frequency map is bounded by 26 characters regardless of input size.

Solution

from collections import Counter

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        # Frequency count for available tiles (e.g., {'A': 2, 'B': 1})
        counts = Counter(tiles)
        
        def backtrack():
            res = 0
            
            # Iterate over unique characters currently in our inventory. 
            # We use list(counts.keys()) to avoid runtime errors if we were modifying keys,
            # though here we only modify values so direct iteration is safe too.
            for char in counts:
                if counts[char] > 0:
                    # Use one instance of this tile
                    counts[char] -= 1
                    
                    # Add the current sequence formed by picking 'char' (count += 1)
                    # Plus all extensions possible from here via recursion.
                    res += 1 + backtrack()
                    
                    # Restore count for backtracking to explore other branches
                    counts[char] += 1
            
            return res

        return backtrack()

Edge Cases Handled

  • Single Character: If input is “V”, the loop runs once, decrements ‘V’, adds 1 + backtrack() (which returns 0), increments back. Result: 1. Correct.
  • All Identical Characters: Input “AAA”. The frequency map has {‘A’: 3}. We only branch on unique key ‘A’. This prevents generating duplicate branches for identical tiles, ensuring we count sequences based on counts rather than indices (e.g., avoiding counting the same permutation multiple times).
  • Mixed Duplicates: Handled naturally by iterating over counts keys. If “AAABBC” is input, only unique letters ‘A’, ‘B’, ‘C’ are iterated in each recursion depth step, ensuring we respect tile limits without redundant computation on identical tiles at the same level.