Vultr DocsLatest Content

Letter Tile Possibilities

Updated on 03 June, 2025
Letter Tile Possibilities header image

Problem Statement

Given a string tiles, where each character represents a tile bearing an uppercase English letter, determine how many unique non-empty sequences of letters you can create using these tiles. Each tile can be used only once per sequence and must be used as many times as it appears in the input.

The goal is to count all possible sequences (of all lengths) that can be formed by rearranging subsets of the given 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

Constraints

  • 1 <= tiles.length <= 7
  • tiles consists of uppercase English letters only.

Approach and Intuition

This problem is a variation of generating permutations with repetition constraints. Since tiles may contain duplicate letters, we must avoid counting duplicate sequences multiple times. The challenge lies in efficiently traversing all valid permutations and subsequences while respecting character frequency limits.

Key Insight:

Each sequence must be unique and non-empty, and letters cannot be reused beyond their given count. This naturally leads us to a backtracking approach that tries each possible character (if still available), recurses, then backtracks.

Step-by-Step Strategy:

  1. Count Frequencies: Use a Counter or frequency map to track how many times each letter appears.

  2. Backtracking: Write a recursive function that:

    • Iterates over all available letters.

    • For each letter with a non-zero count:

      • Decrease its count (simulating use).
      • Recurse to extend the current sequence.
      • Restore the count (backtrack) after recursion.
      • Increase the result counter by 1 at each choice since every non-empty sequence formed is valid.

  3. Avoid Redundancy: Since we process letters based on frequency and avoid recomputing duplicate arrangements, there's no need to explicitly store all sequences—just count them.

Time Complexity:

The maximum number of sequences grows quickly with the number of tiles. Since tiles.length <= 7, a brute-force backtracking approach is acceptable. The upper bound of possible unique permutations is less than 7! = 5040, adjusted down due to repeated letters.

Solutions

  • C++
  • Java
  • Python
cpp 
class TileCalculator {
public:
    int tilePermutationCount(string tiles) {
        unordered_set<string> uniqueCombinations;

        // Ensure sorted tiles for efficient duplication handling
        sort(tiles.begin(), tiles.end());

        // Get total unique permutations count, subtract 1 for empty sequence
        return exploreTileCombinations(tiles, "", 0, uniqueCombinations) - 1;
    }

private:
    int computeFactorial(int n) {
        if (n <= 1) {
            return 1;
        }

        int product = 1;
        for (int i = 2; i <= n; i++) {
            product *= i;
        }
        return product;
    }

    int permutationCount(string& sequence) {
        // Character frequency count
        int frequency[26] = {0};
        for (char c : sequence) {
            frequency[c - 'A']++;
        }

        // Calculate total permutations using character frequencies
        int result = computeFactorial(sequence.length());
        for (int freq : frequency) {
            if (freq > 1) {
                result /= computeFactorial(freq);
            }
        }
        return result;
    }

    int exploreTileCombinations(string& tiles, string current, int index,
                                 unordered_set<string>& combinations) {
        if (index >= tiles.length()) {
            // Add new sequence to set and compute permutations if added successfully
            if (combinations.insert(current).second) {
                return permutationCount(current);
            }
            return 0;
        }

        // Recursive permutations excluding and including current tile
        return exploreTileCombinations(tiles, current, index + 1, combinations) +
               exploreTileCombinations(tiles, current + tiles[index], index + 1, combinations);
    }
};

The solution provided implements the TileCalculator class in C++ to determine the number of possible non-empty sequences that can be formed from a given string of tiles where each tile has a letter on it.

  • tilePermutationCount Function: Main method that initiates the process by taking a string of tiles as input:

    • Uses unordered_set to store unique combinations.
    • Sorts the tile string to manage duplicate characters efficiently.
    • Calls exploreTileCombinations method and adjusts for the count by subtracting 1 to exclude the empty sequence.

  • computeFactorial Function: Helper method that calculates the factorial of a number to aid in permutation calculations:

    • Handles factorial computation iteratively.

  • permutationCount Function: Computes the number of permutations for a given string based on character frequency:

    • Counts frequency of each character.
    • Calculates permutation of the string using the factorial results adjusted by the frequency of each character.

  • exploreTileCombinations Function: Recursive helper method to build and explore all combinations:

    • Excludes and includes the current tile in recursive calls to form all possible combinations.
    • Uses an index to manage current tile in recursion.
    • Adds combinations to the set and calculates permutations if the combination is unique.

This solution accounts for duplicate tiles effectively and ensures that all unique tile combinations are considered. Implementing permutations count based on character frequency helps to optimize the process due to redundant sequences generated by repeating characters.

java 
class Solution {

    public int calculateTilePossibilities(String tiles) {
        Set<String> uniqueSequences = new HashSet<>();

        // Arrange characters to manage duplicates
        char[] tileChars = tiles.toCharArray();
        Arrays.sort(tileChars);
        String orderedTiles = new String(tileChars);

        // Calculate all unique permutations
        return exploreTiles(orderedTiles, "", 0, uniqueSequences) - 1;
    }

    private int computeFactorial(int n) {
        if (n <= 1) {
            return 1;
        }

        int factorialResult = 1;
        for (int i = 2; i <= n; i++) {
            factorialResult *= i;
        }
        return factorialResult;
    }

    private int calculatePermutations(String sequence) {
        // Frequency count of each character
        int[] frequency = new int[26];
        for (char c : sequence.toCharArray()) {
            frequency[c - 'A']++;
        }

        // Compute permutations using factorial
        int permutations = computeFactorial(sequence.length());
        for (int freq : frequency) {
            permutations /= computeFactorial(freq);
        }
        return permutations;
    }

    private int exploreTiles(
        String tiles,
        String currentSequence,
        int index,
        Set<String> uniqueSequences
    ) {
        if (index >= tiles.length()) {
            // Capture unique permutations of the sequence
            if (uniqueSequences.add(currentSequence)) {
                return calculatePermutations(currentSequence);
            }
            return 0;
        }

        // Include or exclude the current character in subsets
        return (
            exploreTiles(tiles, currentSequence, index + 1, uniqueSequences) +
            exploreTiles(tiles, currentSequence + tiles.charAt(index), index + 1, uniqueSequences)
        );
    }
}

The problem Letter Tile Possibilities in Java involves generating all unique sequences that can be formed from a given set of tiles where each tile is a letter. The solution aims at calculating the number of possible non-empty sequences by utilizing backtracking to explore all possible combinations of the tiles and then calculating unique permutations for each combination.

Understanding the Approach:

  • Initialize a HashSet to keep track of unique sequences generated.
  • Convert string tiles to a sorted character array to efficiently handle duplicate sequences and convert it back to string for easier manipulation.
  • Use recursive backtracking function exploreTiles to construct all possible sequences by deciding, for each tile, whether to include it in the current sequence or not.
  • For each unique sequence generated, calculate its possible permutations taking into account the multiplicity of each character, which prevents permutations of the same letters being counted multiple times.

Detailed Breakdown:

  • The exploreTiles method explores each tile possibility by either including or excluding the current character. The sequences are constructed incrementally and checked against existing sequences stored in a set to avoid duplicates.
  • For every unique sequence discovered, calculatePermutations computes the total number of permutations possible for that sequence based on character frequencies. It uses a helper method computeFactorial which calculates factorial of a given number, utilized for permutation calculation.
  • The recursive exploration process continues until all sequences are evaluated. It returns the count of unique permutations accumulated during the process, excluding a count for the empty sequence, adjusted at the end of calculateTilePossibilities method, ensuring only non-empty sequences are counted.

Overall, the Java solution uses efficient data structures and recursive techniques to solve the complex problem of permuting and combining tile letters into unique sequences, respecting character frequencies to ensure correctness of permutation counts. This approach ensures optimal performance for generating and counting distinct sequences from given tiles.

python 
class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        seen_tiles = set()

        # Sort tiles to manage duplicates more effectively
        organized_tiles = "".join(sorted(tiles))

        # Calculate unique combinations of those tiles including permutations
        return self._explore_tiles(organized_tiles, "", 0, seen_tiles) - 1

    def _compute_factorial(self, n: int) -> int:
        if n <= 1:
            return 1

        factorial_result = 1
        for number in range(2, n + 1):
            factorial_result *= number
        return factorial_result

    def _calculate_permutations(self, sequence: str) -> int:
        # Use factorial concept for permutations calculation
        factorial_total = self._compute_factorial(len(sequence))

        # Adjust for multiple occurrences of characters
        from collections import Counter
        for freq in Counter(sequence).values():
            factorial_total //= self._compute_factorial(freq)

        return factorial_total

    def _explore_tiles(
        self, tiles: str, current: str, index: int, seen_tiles: set
    ) -> int:
        if index >= len(tiles):
            # Count permutations of a new unique sequence
            if current not in seen_tiles:
                seen_tiles.add(current)
                return self._calculate_permutations(current)
            return 0

        # Recursive exploration including and excluding the current character
        return self._explore_tiles(
            tiles, current, index + 1, seen_tiles
        ) + self._explore_tiles(tiles, current + tiles[index], index + 1, seen_tiles)

The Python solution provided solves the problem of calculating the number of unique sequences that can be formed using the letters from a given set of tiles. Here's an overview of how the solution works:

  • First, a class named Solution is defined with a method numTilePossibilities, which initializes a set for tracking seen tile combinations and sorts the tiles to help manage duplicates more effectively.

  • The main logic of generating tile combinations is handled by the recursive function _explore_tiles. Here, combinations of the tiles are formed by choosing to either include or exclude each character, represented by the index parameter.

  • The method _calculate_permutations counts the unique permutations of any given sequence based on the frequency of each character, employing the factorial concept. Factorials are computed in the helper method _compute_factorial.

  • The recursion terminates when the index exceeds the length of tiles, at which point the permutations of the current sequence are calculated if it has not been processed before.

  • The final return in numTilePossibilities subtracts one from the results of _explore_tiles to exclude the empty sequence that is inherently counted.

By this method, all possible unique combinations of the input tiles are effectively generated and counted. The solution leverages sorting, set operations, recursion, and combinatorial mathematics (factorials and permutations) to manage and solve the problem.

Comments

No comments yet.