Home » Computer Science » Problems

Letter Tile Possibilities

February 17, 2025 · 5 min · backtracking · counting · hash-table · leetcode · string · sorting · video | 🖍️

Practice on:

Table of Contents

Problem

You have n 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.

Examples

Example 1:

Input: tiles = "AAB"
Output: 8
Explanation: The possible sequences are "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA".

Example 2:

Input: tiles = "AAABBC"
Output: 188

Example 3:

Input: tiles = "V"
Output: 1

Solution

Video explanation

Here is the video explaining below methods in detail. Please check it out:

Method 1 - Mathematical

The mathematical approach relies on permutations and combinatorics. The idea is to count the number of sequences for all possible lengths ( k ), from ( 1 ) to ( n ) (where ( n ) is the total number of tiles). For each length ( k ):

Choose ( k ) tiles (including duplicates) from ( n ) tiles.
Determine the number of unique permutations for the chosen subset, accounting for duplicate characters.
Use the multiset permutation formula: $\text{Permutations} = \frac{k!}{f_1! \cdot f_2! \cdot \dots \cdot f_m!}$ Here, ( f_1, f_2, …, f_m ) are the frequencies of the unique characters in the subset.
For each ( k ) (length of the sequence to consider), generate all valid combinations of characters.
For every combination:
- Count the frequencies of each unique character.
- Calculate the number of unique permutations using the formula.
Sum the counts for all lengths ( k ) to get the total.

Generating all subsets and calculating factorials at each step is computationally expensive (especially for duplicates).
A fixed formula makes handling duplicates tedious.

Complexity

⏰ Time complexity: O(2^n).n
🧺 Space complexity: O(n)

Method 2 - Backtracking by sorting

To solve the problem, we need to calculate all possible permutations of the given letters while considering duplicate occurrences of the same letter. If the input has duplicate letters, we must ensure the resulting sequences do not contain duplicate permutations.

So, initially:

We’ll sort the input letters first—this makes it easier to skip duplicates within the recursion.
Start with an empty sequence and recursively build sequences by adding one tile at a time.

Here are the steps:

Sort the letters to group duplicates together. This will help in skipping over duplicates efficiently during recursion.
Use a used array to track which characters are in the current path.
For each recursive call:
- Explore each tile that hasn’t already been used, ensuring we skip duplicates if the current tile is the same as the previous one.
Continue building permutations and backtrack after exploring deeper paths.

Code

Java

class Solution {
    public int numTilePossibilities(String tiles) {
        char[] tArr = tiles.toCharArray();
        Arrays.sort(tArr); // Sort to handle duplicates
        return backtrack(tArr, new boolean[tArr.length]);
    }
    
    private int backtrack(char[] tArr, boolean[] used) {
        int ans = 0;
        for (int i = 0; i < tArr.length; i++) {
            // Skip already used or duplicate entries
            if (used[i] || (i > 0 && tArr[i] == tArr[i - 1] && !used[i - 1])) {
                continue;
            }
            used[i] = true;
            ans += 1 + backtrack(tArr, used); // Count current and recursive paths
            used[i] = false;
        }
        return ans;
    }
}

Python

class Solution {
    public int numTilePossibilities(String tiles) {
        char[] tArr = tiles.toCharArray();
        Arrays.sort(tArr); // Sort to handle duplicates
        return backtrack(tArr, new boolean[tArr.length]);
    }
    
    private int backtrack(char[] tArr, boolean[] used) {
        int ans = 0;
        for (int i = 0; i < tArr.length; i++) {
            // Skip already used or duplicate entries
            if (used[i] || (i > 0 && tArr[i] == tArr[i - 1] && !used[i - 1])) {
                continue;
            }
            used[i] = true;
            ans += 1 + backtrack(tArr, used); // Count current and recursive paths
            used[i] = false;
        }
        return ans;
    }
}

Complexity

⏰ Time complexity: O(n.n!), where n is the number of tiles. This is because generating permutations involves factorial growth.
🧺 Space complexity: O(n), for the recursion stack and O(n) for the used array.

Method 3 - Backtracking using frequency map

We can use a frequency map. Lets take input as AAB, the the frequency map count as {A: 2, B: 1}.

The backtracking approach explores all possible sequences directly by constructing paths incrementally. At each step, we decide whether to use a particular tile, while keeping track of which tiles are available using a frequency map (or array).

Approach

Use a frequency map to store the count of each character in tiles.
Start with an empty sequence and recursively:
- Choose a tile, decrement its count, and add it to the sequence.
- Explore further sequences by recursively calling the function.
- Restore the tile’s count (backtrack) once all paths for that choice are explored.
Count every valid sequence during the exploration.

Code

Java

class Solution {
    public int numTilePossibilities(String tiles) {
        // Create a frequency array (26 slots for A-Z)
        int[] count = new int[26];
        for (char c : tiles.toCharArray()) {
            count[c - 'A']++;  // Increment frequency of the respective character
        }
        
        // Start backtracking
        return backtrack(count);
    }

    private int backtrack(int[] count) {
        int total = 0;
        for (int i = 0; i < 26; i++) {  // Iterate over all characters
            if (count[i] > 0) {  // If character is available
                count[i]--;  // Choose the character
                total++;  // Add 1 for the current sequence
                total += backtrack(count);  // Recurse for further sequences
                count[i]++;  // Backtrack: restore the character count
            }
        }
        return total;
    }
}

Python

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        # Create a frequency Counter
        count = Counter(tiles)
        
        def backtrack() -> int:
            total = 0
            for tile in count:  # Iterate over all characters in the Counter
                if count[tile] > 0:  # If the character is available
                    count[tile] -= 1  # Choose the character
                    total += 1  # Add 1 for the current sequence
                    total += backtrack()  # Recurse for further sequences
                    count[tile] += 1  # Backtrack: restore the count
            return total
        
        return backtrack()

Complexity

⏰ Time complexity: O(k.k!), where k is the number of distinct characters. For each character, we can choose to include or exclude it at every level of recursion. The worst-case time complexity is proportional to the total number of unique sequences, which is k.k!.
🧺 Space complexity: O(n), where n is the length of the tile string. 1The frequency map uses O(k) ), but k = 26 in this problem.

comments powered by Disqus