Letter Tile Possibilities

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.

For example:

tiles = "AAB"
Output: 8
Explanation: The possible sequences are "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA".

tiles = "AAABBC"
Output: 188

tiles = "V"
Output: 1

from collections import Counter

def numTilePossibilities(tiles: str) -> int:
    count = Counter(tiles)
    result = set()

    def backtrack(combination):
        if combination:
            result.add(combination)

        for char in count:
            if count[char] > 0:
                count[char] -= 1
                backtrack(combination + char)
                count[char] += 1

    backtrack("")
    return len(result)

Explanation

1. Initialization:

   • We use Counter to count the occurrences of each tile.
   • result is a set to store unique sequences.

2. Backtracking Function:

   • The backtrack function generates sequences recursively.
   • It takes a combination string as input, representing the current sequence.
   • If the combination is not empty, it's added to the result set.
   • The function iterates through each unique character (char) in the count:
     • If the count of char is greater than 0:
       • Decrement the count of char.
       • Recursively call backtrack with the updated combination (adding char to it).
       • Increment the count of char to backtrack and explore other possibilities.

3. Main Logic:

   • Call the backtrack function with an empty string to start generating sequences.
   • Return the length of the result set, which contains all unique non-empty sequences.

Example

Let's trace the execution with tiles = "AAB":

1. count = {"A": 2, "B": 1}

2. backtrack(""):

   • char = "A": count["A"] = 1, backtrack("A")
     • result.add("A")
     • char = "A": count["A"] = 0, backtrack("AA")
       • result.add("AA")
       • char = "B": count["B"] = 1, backtrack("AAB")
         • result.add("AAB")
         • backtrack("AAB") returns
       • count["B"] = 0
       • backtrack("AA") returns
     • count["A"] = 1
     • char = "B": count["B"] = 0, backtrack("AB")
       • result.add("AB")
       • char = "A": count["A"] = 1, backtrack("ABA")
         • result.add("ABA")
         • backtrack("ABA") returns
       • count["A"] = 0
       • backtrack("AB") returns
     • count["B"] = 1
     • backtrack("A") returns
   • count["A"] = 2
   • char = "B": count["B"] = 0, backtrack("B")
     • result.add("B")
     • char = "A": count["A"] = 1, backtrack("BA")
       • result.add("BA")
       • char = "A": count["A"] = 0, backtrack("BAA")
         • result.add("BAA")
         • backtrack("BAA") returns
       • count["A"] = 1
       • backtrack("BA") returns
     • count["A"] = 2
     • backtrack("B") returns
   • count["B"] = 1
   • backtrack("") returns

3. return len(result) which is 8.

Big O Analysis

• Time Complexity: O(∑(P(n, i))), where i ranges from 1 to n, and P(n, i) is the number of i-permutations of n. In the worst-case scenario, where all tiles are distinct, this complexity grows factorially with the length of the tiles string. This is because each tile can be used in different positions, leading to a combinatorial explosion of possibilities.
• Space Complexity: O(N), where N is the number of possible sequences. This space is used to store the unique sequences in the result set and the call stack during recursion. In the worst case, this space can grow significantly with the length of the input string, as the number of possible sequences increases factorially.