Problem Informations

• Problem Index: 1079
• Problem Link: Letter Tile Possibilities
• Topics: Hash Table, String, Backtracking, Counting

Problem Description

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.

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 \leq \text{tiles.length} \leq 7$
• tiles consists of uppercase English letters.

Intuition

The problem presents a seemingly straightforward task of generating all possible non-empty sequences of letters from given tiles. The intuitive approach is to consider each tile and explore the possible sequences that can be created starting with that tile. Given the constraint that the length of the string of tiles is relatively small (maximum length of 7), a backtracking approach can effectively enumerate all possible combinations, taking into account the repetition of characters.

Approach

The solution uses a backtracking mechanism to explore all potential sequences formed by the tiles. The key steps are as follows:

1. Frequency Counting: The algorithm first counts the frequency of each letter present in the input string tiles. This count is maintained in a frequency array of size 26, corresponding to the 26 uppercase English letters. This allows us to efficiently check the availability of each tile while generating sequences.

2. Backtracking Function: A recursive function backtrack is used to construct possible sequences. This function operates under the principle of decision-making, where at each step, a decision is made whether to include a particular letter in the current sequence or not.

   • Recursion and Backtracking: For each possible letter, if at least one tile of that letter is available (frequency greater than zero), the algorithm includes it in the sequence and decrements its frequency. It then recursively explores further sequences by calling backtrack again. After returning from the recursion, the frequency is incremented back, effectively “undoing” the decision, thereby exploring alternative sequences that do not include the recent letter.
   • Sequence Counting: Each time the function completes an iteration through all potential starting letters for a particular sequence position, it increments a global counter ans to account for another valid sequence.

3. Result Calculation: The backtracking process is initiated from an initial state where no tiles are chosen (an empty sequence), and the frequency map reflects the count of each tile in the input. Finally, the counter ans, which accumulates the total number of non-empty sequences, is returned.

This approach efficiently generates all possible non-empty sequences of letters by leveraging the backtracking technique, which inherently accounts for permutations and combinations of letters, including repeated sequences when letters have multiple occurrences.

Code

C++

class Solution {
public:
    // Initialize the counter for number of possible sequences
    int ans = -1;

    // Backtracking function to explore all possible sequences
    void backtrack(vector<int>& frequency, int len, int idx) {
        // Iterate through all possible letters
        for (int i = 0; i < 26; i++) {
            // If no more of this letter left, skip it
            if (frequency[i] == 0) continue;
            
            // Use one instance of the current letter
            frequency[i]--;
            // Recursively call backtrack to form longer sequences
            backtrack(frequency, len, idx + 1);
            // Backtrack: restore the letter count
            frequency[i]++;
        }
        // Increment the sequence counter
        ans++;
    }
    
    int numTilePossibilities(string tiles) {
        // Initialize letter frequency array for 26 uppercase letters
        vector<int> frequency(26, 0);

        // Count each letter in the input tiles
        for (char c : tiles) {
            frequency[c - 'A']++;
        }

        // Start backtracking from the initial state
        backtrack(frequency, tiles.size(), 0);

        return ans;
    }
};

Python

class Solution:
    # Initialize the counter for number of possible sequences
    def __init__(self):
        self.ans = -1

    # Backtracking function to explore all possible sequences
    def backtrack(self, frequency, len, idx):
        # Iterate through all possible letters
        for i in range(26):
            # If no more of this letter left, skip it
            if frequency[i] == 0:
                continue
            
            # Use one instance of the current letter
            frequency[i] -= 1
            # Recursively call backtrack to form longer sequences
            self.backtrack(frequency, len, idx + 1)
            # Backtrack: restore the letter count
            frequency[i] += 1
        
        # Increment the sequence counter
        self.ans += 1

    def numTilePossibilities(self, tiles):
        # Initialize letter frequency array for 26 uppercase letters
        frequency = [0] * 26

        # Count each letter in the input tiles
        for c in tiles:
            frequency[ord(c) - ord('A')] += 1

        # Start backtracking from the initial state
        self.backtrack(frequency, len(tiles), 0)

        return self.ans

Complexity

• Time complexity: The time complexity is $O(26^n \cdot n!)$, where $n$ is the length of the input string tiles. This is because the function explores every possible permutation of the tiles, including duplicates and all possible lengths less than or equal to $n$. There are a maximum of $26^n$ recursive calls due to the 26 possible letters, and in each recursive call, we iterate over the frequency array which has a maximum of $n$ elements (since $n \leq 7$, the factorial $n!$ dominates).

• Space complexity: The space complexity is $O(n)$, where $n$ is the length of the tiles. The space is primarily used by the call stack during the recursive backtracking process. The depth of the recursion stack is bounded by the length of the tiles, which is up to 7.