Problem statement

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

Solution 1

Problem constraints are small enough to make dfs with backtracking. Idea to insert each new symbol between build or not insert it at all.

Complexity

It is O(n!) for time and space.

Code

class Solution:
    def numTilePossibilities(self, tiles):
        self.ans = []
        def dfs(build, left):
            if left == "":
                self.ans += [build]
                return
            
            l = left[-1]
            for i in range(len(build) + 1):
                dfs(build[:i] + l + build[i:], left[:-1])
            dfs(build, left[:-1])
            
        dfs("", "".join(tiles))
        return len(set(self.ans)) - 1

Solution 2

Actually we can solve it with combinatorics with dp(i, l) state, where i is index of unique letter and l is total length of word we want to create. How we can create it? We can put j <= min(B[i], l) letters to any j out of l places.

Complexity

Let m = len(tiles) and n = len(Counter(tiles)), then time complexity is O(m^2 n).

Code

MOD, M = 10**9 + 7, 10**5
F = [1]*(M+1)
for i in range(1, M+1):
    F[i] = (F[i-1] * i) % MOD

I = [1]*M + [pow(F[M], MOD - 2, MOD)]
for i in range(M-1, 0, -1):
    I[i] = I[i+1]*(i+1) % MOD

class Solution:
    def numTilePossibilities(self, tiles):
        B = list(Counter(tiles).values())
        m = len(tiles)
        
        @lru_cache(None)
        def dp(i, l):
            if l == 0: return 1
            if i >= len(B): return 0
            return sum(dp(i+1, l-j)*F[l]*I[j]*I[l-j] for j in range(min(B[i], l) + 1))
        
        return sum(dp(0, i) for i in range(1, m+1)) % MOD