Leetcode 1079. Letter Tile Possibilities

Table of Contents

This is the daily question of leetcode in 2025-02-17.

Problem Description
#

Given $n$ tiles (letters, e.g. $AAB$), count all of possible unique sequences that can be formed using these letters.

Intuition
#

When we see a problem related to finding sequences, the first algorithm that comes to mind is backtracking.

Approach
#

Count the frequency of each tile (letter).
Use DFS to explore all possible sequences by decrementing letter frequency and recursively calling the function.
Backtrack by restoring the frequency to ensure all possibilities are considered.

Time Complexity: $O(N!)$ since we are exploring all unique sequences.

Code
#

class Solution {
public:
    // DFS function to count all possible sequences
    int countSequences(unordered_map<char, int>& frequency){
        int result = 0;

        // Iterate over all available letters
        for(auto& pair: frequency){
            char letter = pair.first;
            if (frequency[letter] > 0){ //only deal with letter that are still available
                frequency[letter] --;  // use this letter
                result += countSequences(frequency) + 1; // Recursive call and count this sequence
                frequency[letter] ++; //backtracking, restore the frequency of the letter
            }
        }
        return result;
    }
    int numTilePossibilities(string tiles) {
        unordered_map<char, int> frequency; //To record frequency of each letter
        for(int i = 0; i < tiles.length(); i++){
            frequency[tiles[i]]++;
        }
        return countSequences(frequency);
    }
};