We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Letter Tile Possibilities

Difficulty: Medium

Problem Description

Given n tiles, where each tile has one letter tiles[i] printed on it, return the number of possible non-empty sequences of letters that can be made using the letters printed on those tiles.

Key Insights

  • Each tile can be used in different sequences.
  • Duplicate letters must be accounted for to avoid counting the same sequence multiple times.
  • The problem can be solved using backtracking to explore all possible combinations of letters.

Space and Time Complexity

Time Complexity: O(n * 2^n) - where n is the number of unique letters. Space Complexity: O(n) - for the recursion stack.

Solution

To solve the problem, we can use a backtracking approach. We keep track of the frequency of each letter using a hash table. At each step, we generate sequences by choosing one letter at a time and recursively building the rest of the sequence. By keeping track of used letters, we ensure that we do not form duplicate sequences. The total count is incremented for every valid sequence generated.

Code Solutions

def numTilePossibilities(tiles):
    from collections import Counter

    def backtrack(counter):
        total = 0
        for letter in counter:
            if counter[letter] > 0:
                # Use this letter
                total += 1
                counter[letter] -= 1
                total += backtrack(counter)
                # Backtrack - restore the letter count
                counter[letter] += 1
        return total

    tile_count = Counter(tiles)
    return backtrack(tile_count)

# Example Usage
print(numTilePossibilities("AAB"))  # Output: 8
← Back to All Questions