1079.Letter_Tile_Possibilities(Medium).md

1079. Letter Tile Possibilities (Medium)

Date and Time: Feb 18, 2025, 1:06 (EST)

Link: https://leetcode.com/problems/letter-tile-possibilities

Question:

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.

Example 1:

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

Example 2:

Input: tiles = "AAABBC"
Output: 188

Example 3:

Input: tiles = "V"
Output: 1

Constraints:

• 1 <= tiles.length <= 7

• tiles consists of uppercase English letters.

Walk-through:

Count each char in tiles and save their counts into dp[]. We need to save the ORD of each letter into dp. Then we run DFS to find the total possibilities we can get, each time, we start from A, we use it and reduce the count in dp[], next we run DFS with this new dp[] and find the total counts. After we finish, increment this count back, so we can start with other letters to form combination.

Python Solution:

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        # Count each char with their count into hashmap{char: count}
        # Run DFS with a list, each time if we use a char, we decrement the count of that char on the list, then run DFS with the list. After we are done, remember to add the count back

        # TC: O(n!), n=len(tiles), SC: O(1)
        dp = [0] * 26
        # Build dp
        for tile in tiles:
            dp[ord(tile) - ord("A")] += 1
        def dfs(dp):
            count = 0
            # Consume char to permutate
            for i in range(26):
                if not dp[i]:
                    continue
                dp[i] -= 1
                count += dfs(dp) + 1
                dp[i] += 1
            return count

        return dfs(dp)

Time Complexity: $O(n!)$
Space Complexity: $O(1)$