All prompts are owned by LeetCode. To view the prompt, click the title link above.
First completed : February 17, 2025
Last updated : February 17, 2025
Related Topics : Hash Table, String, Backtracking, Counting
Acceptance Rate : 83.65 %
Beats 100% according to LC. I presume this is because most aren't optimizing it with multinomials and are instead simulating every possible ordering.
Optimizations I've used:
- Uses the frequencies of each character rather than the characters themselves
- DFS's using the frequencies used instead of simulating the final strings
- Uses multinomials to calculate how many arrangements of the selected characters instead of simulating them
class Solution:
def dfs(self, tiles: List[int], used: List[int], used_sum: int) -> int :
# Calculates the number of states using the multinomial coefficient
# to avoid propogating to all cases
if not tiles :
return factorial(used_sum) // prod([factorial(x) for x in used])
x = tiles.pop()
output = self.dfs(tiles, used, used_sum) # case: we don't use this value
for i in range(1, x + 1) : # case: we use "i" number of this value
used.append(i)
output += self.dfs(tiles, used, used_sum + i)
used.pop()
tiles.append(x)
return output
def numTilePossibilities(self, tiles: str) -> int:
return self.dfs(list(Counter(tiles).values()), [], 0) - 1