[MEDIUM] #1079 - Letter Tile Possibilities

[hackdartstorm]

🎯 Problem: Letter Tile Possibilities

📖 The Real Problem

You have a collection of letter tiles, where each tile has one uppercase English letter. Your task is to find all possible non-empty sequences of letters that can be formed using these tiles.

Key constraints:

• Each tile can only be used ONCE per sequence
• Sequences of any length are valid (1 letter, 2 letters, up to all tiles)
• Order matters ("AB" and "BA" are different sequences)
• Return the COUNT of all unique sequences possible

Why this problem exists:

• Tests understanding of permutations and combinations
• Requires handling duplicate letters correctly
• Combines backtracking with set operations for uniqueness

💡 Why This Matters

Real-world applications:

• Word games like Scrabble, Boggle, Wordscapes
• Password generation from character sets
• DNA sequence analysis - finding all possible subsequences
• Anagram solvers and word puzzle helpers

Skills you'll develop:

• ✅ Backtracking algorithm
• ✅ Permutation generation
• ✅ Handling duplicates in combinatorics
• ✅ Set operations for uniqueness
• ✅ Recursive problem solving

📋 Contributor Tasks

Step 1: Understand the Problem

1. Take a simple example: tiles = "AAB"
2. List all possible sequences manually:
   • Length 1: A, B
   • Length 2: AA, AB, BA
   • Length 3: AAB, ABA, BAA
3. Count them: 2 + 3 + 3 = 8 total sequences

Step 2: Plan Your Approach

1. Use backtracking to generate all sequences
2. Use a set to track unique sequences
3. For each position, try each available tile
4. Mark tiles as used, recurse, then unmark (backtrack)

Step 3: Implement the Solution

1. Create a set to store unique sequences
2. Create a recursive backtracking function
3. Track which tiles are used (boolean array or counter)
4. At each step, try all unused tiles
5. Add each valid sequence to the set
6. Return the size of the set

Step 4: Test Your Solution

1. Test with single letter: "A"
2. Test with all same letters: "AAA"
3. Test with all different: "ABC"
4. Test with duplicates: "AAB"
5. Test with longer strings

✅ Expected Outcome

Function Signature:

def numTilePossibilities(tiles):
    """
    Count all possible non-empty letter sequences from tiles.
    
    Args:
        tiles: str - string of uppercase letters
    
    Returns:
        int: count of unique possible sequences
    
    Example:
        >>> numTilePossibilities("AAB")
        8
    """

Expected Behavior:

• ✅ Counts ALL possible sequences (any length 1 to n)
• ✅ Handles duplicate letters correctly
• ✅ Order matters (AB ≠ BA)
• ✅ Each tile used at most once per sequence
• ✅ Returns count, not the sequences themselves

Example Test Cases:

# Test 1: Single letter
numTilePossibilities("A")  # Returns: 1 (just "A")

# Test 2: Two different letters
numTilePossibilities("AB")  # Returns: 3 (A, B, AB, BA... wait, that's 4)
# Actually: A, B, AB, BA = 4

# Test 3: Two same letters
numTilePossibilities("AA")  # Returns: 2 (A, AA)

# Test 4: Example from problem
numTilePossibilities("AAB")  # Returns: 8
# Sequences: A, B, AA, AB, BA, AAB, ABA, BAA

# Test 5: All different
numTilePossibilities("ABC")  # Returns: 15
# Length 1: A, B, C (3)
# Length 2: AB, AC, BA, BC, CA, CB (6)
# Length 3: ABC, ACB, BAC, BCA, CAB, CBA (6)
# Total: 15

📚 Additional Context & References

Understanding the Problem

Key Insight:
This is a permutation problem with a twist - we need permutations of ALL lengths, not just full length.

Mathematical Formula (for all unique letters):

• For n unique letters:
• Total = nP1 + nP2 + nP3 + ... + nPn
• Where nPk = n! / (n-k)!

With Duplicates:

• Need to avoid counting duplicate sequences
• Use a set to track unique sequences

Backtracking Template

def backtrack(path, remaining):
    # Base case: no more tiles
    if not remaining:
        return
    
    # Try each remaining tile
    for i, tile in enumerate(remaining):
        # Choose
        new_path = path + tile
        
        # Add to results (if not empty)
        if new_path:
            results.add(new_path)
        
        # Explore
        backtrack(new_path, remaining[:i] + remaining[i+1:])
        
        # Backtrack (implicit in this approach)

Hints (Use Only If Stuck!)

💡 Hint 1

Think about building sequences one letter at a time. At each step, which tiles can you use?

💡 Hint 2

Use a set to automatically handle duplicate sequences.

💡 Hint 3

For each position in your sequence, try every tile that hasn't been used yet.

Complexity Analysis

Time Complexity: O(n! × n)

• In worst case (all unique letters), generate all permutations
• n! permutations, each of length up to n
• Set operations add overhead

Space Complexity: O(n! × n)

• Store all unique sequences in set
• Each sequence up to length n
• Recursion stack: O(n)

Alternative Approaches

Approach 1: Backtracking with Set (Recommended)

• Generate all sequences, store in set
• Simple and clear

Approach 2: Counting with Math

• Count frequency of each letter
• Use combinatorics formula
• More complex but potentially faster

Related Problems

Once you solve this, try:

• Permutations - Generate all permutations
• Permutations II - Handle duplicates
• Letter Combinations of Phone Number - Similar backtracking
• Combination Sum - Different backtracking pattern

Helpful Resources

• Backtracking Algorithm
• Permutations with Duplicates
• LeetCode 1079 - Letter Tile Possibilities

📝 Notes

• Input contains only uppercase English letters
• Tiles string length: 1 to 7 (small enough for backtracking)
• Each tile can be used only once per sequence
• Empty sequence doesn't count
• Return count, not the actual sequences

---

Ready to contribute?

1. Fork the repository
2. Create your solution file
3. Test with provided examples
4. Submit a pull request!

File Location: exercises/1000_programs/medium/1079_letter_tile_possibilities.py

🚀 Happy coding!