LeetCode 1079 - Letter Tile Possibilities

The problem asks us to count all possible non-empty sequences that can be formed from a set of letter tiles, where each tile has a single uppercase letter. The input is a string tiles representing the letters available on the tiles.

leetcodemediumhash-tablestringbacktrackingcounting

LeetCode Problem 1079

Difficulty: 🟡 Medium
Topics: Hash Table, String, Backtracking, Counting

Solution

Problem Understanding

The problem asks us to count all possible non-empty sequences that can be formed from a set of letter tiles, where each tile has a single uppercase letter. The input is a string tiles representing the letters available on the tiles. The output is an integer representing the total number of distinct sequences that can be made by using one or more tiles in any order.

Each sequence can use each tile at most once, but multiple tiles with the same letter are distinguishable only by count. For example, in "AAB", the two 'A' tiles allow sequences like "AA" and "AAB", but the order of the 'A' tiles does not produce new sequences beyond what letter ordering already creates.

The constraints are small: 1 <= tiles.length <= 7, which indicates that brute-force generation of sequences is feasible but can be optimized by avoiding duplicates using a counting strategy. Important edge cases include all letters being identical, a single letter, and tiles with multiple repeated letters. These cases test the handling of duplicates and correct counting.

Approaches

The brute-force approach would generate all possible sequences using permutations of length 1 through n. This guarantees correctness because it explores every possible sequence. However, it is inefficient due to generating many duplicate sequences, particularly when tiles contain repeated letters. This would require filtering duplicates using a set, which adds overhead. The factorial growth in the number of sequences (up to 7! = 5040 for length 7) makes it suboptimal.

The optimal approach leverages backtracking with a frequency count of each letter. Instead of generating all sequences blindly, we track how many tiles of each letter remain. At each step, we choose a letter, decrement its count, recurse to build longer sequences, and then backtrack by restoring the count. This ensures no duplicate sequences are counted, and the small input size ensures the algorithm runs efficiently.

Approach Time Complexity Space Complexity Notes
Brute Force O(n!) O(n!) Generates all permutations, filters duplicates
Optimal O(∑_{k=1}^n n! / (c1! c2! ... ck!)) O(n) Backtracking using frequency count avoids duplicates efficiently

Algorithm Walkthrough

  1. Count letter frequencies: Build a hash map (or array for A-Z) to store how many tiles of each letter are available. This simplifies the decision process at each step.
  2. Define recursive backtracking function: The function takes the current frequency map and attempts to add one tile of each letter to the current sequence.
  3. Iterate through letters: For each letter, if its count is greater than 0, decrement the count, count the sequence formed by adding this letter, and recursively explore further sequences.
  4. Backtrack: After recursion, increment the count of the current letter to restore the state for other choices.
  5. Aggregate results: Sum the counts returned from recursive calls to get the total number of sequences.

Why it works: The algorithm ensures that every possible sequence is explored exactly once, thanks to the frequency count mechanism. Backtracking guarantees that no letters are overused, and recursion explores all valid lengths.

Python Solution

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        from collections import Counter

        def backtrack(counter: Counter) -> int:
            total = 0
            for letter in counter:
                if counter[letter] > 0:
                    counter[letter] -= 1
                    total += 1 + backtrack(counter)
                    counter[letter] += 1
            return total

        tile_count = Counter(tiles)
        return backtrack(tile_count)

The Python solution first counts how many of each letter exist using Counter. The backtrack function recursively tries each letter that still has remaining tiles, adding one for the sequence formed and recursing to count longer sequences. After each recursion, the letter count is restored to allow exploration of other sequences. This approach ensures all sequences are counted exactly once without generating duplicates.

Go Solution

func numTilePossibilities(tiles string) int {
    freq := make(map[rune]int)
    for _, c := range tiles {
        freq[c]++
    }

    var backtrack func(map[rune]int) int
    backtrack = func(counter map[rune]int) int {
        total := 0
        for c := range counter {
            if counter[c] > 0 {
                counter[c]--
                total += 1 + backtrack(counter)
                counter[c]++
            }
        }
        return total
    }

    return backtrack(freq)
}

The Go solution mirrors the Python approach. We use a map of runes to count letter frequencies. The recursive backtrack function handles each letter with remaining tiles, adding to the total sequences and recursively counting longer sequences. Backtracking restores the counts, ensuring all sequences are considered without duplicates.

Worked Examples

Example: "AAB"

Step through backtracking:

Step Letter Chosen Counter After Sequences Counted
1 'A' {'A':1,'B':1} 1 ("A")
2 'A' {'A':0,'B':1} 1 ("AA")
3 'B' {'A':0,'B':0} 1 ("AAB")
2 'B' {'A':1,'B':0} 1 ("AB")
1 'B' {'A':2,'B':0} 1 ("B")
2 'A' {'A':1,'B':0} 1 ("BA")

Total sequences = 8, matching the example.

Complexity Analysis

Measure Complexity Explanation
Time O(∑_{k=1}^n n! / (c1! c2! ... ck!)) Each unique permutation is explored once. Factorial terms account for repeated letters.
Space O(n) Maximum recursion depth equals the number of tiles. Counter/map takes O(n) space.

The time complexity considers all unique sequences generated. The space complexity is linear due to recursion stack and frequency map.

Test Cases

# Basic examples
assert Solution().numTilePossibilities("AAB") == 8  # given example
assert Solution().numTilePossibilities("AAABBC") == 188  # given example
assert Solution().numTilePossibilities("V") == 1  # single letter

# Edge and boundary cases
assert Solution().numTilePossibilities("AAAAAAA") == 127  # all same letters
assert Solution().numTilePossibilities("ABCDEFG") == 13699  # all unique letters
assert Solution().numTilePossibilities("AB") == 4  # small input
assert Solution().numTilePossibilities("ABB") == 8  # repeated letter, not all same
Test Why
"AAB" Checks handling of repeated letters and multiple sequence lengths
"AAABBC" Larger input with several repeated letters, tests scaling
"V" Single-letter input, minimal edge case
"AAAAAAA" All identical letters, maximal repetition
"ABCDEFG" All unique letters, maximal length and distinct sequences
"AB" Small input, ensures basic permutations are correct
"ABB" Mixed repetition, tests duplicate sequence handling

Edge Cases

All letters identical: If tiles are "AAAA", sequences can only differ by length. The algorithm correctly counts sequences from length 1 to n using backtracking, ensuring no duplicates.

Single letter input: "V" only allows one sequence, the letter itself. The recursion correctly returns 1 without further branching.

Maximum tile length with unique letters: "ABCDEFG" tests the algorithm's ability to explore all factorial-length sequences without exceeding time limits. Backtracking efficiently generates each unique sequence exactly once, handling the factorial growth correctly.