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.

Difficulty: interview

Starter code:

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        

Solutions:
class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        res = 0
        freqs = [f + 1 for f in Counter(tiles).values()]
        for t in itertools.product(*map(range, freqs)):
            n = sum(t)
            subtotal = math.factorial(n)
            for freq in t:
                subtotal //= math.factorial(freq)
            res += subtotal
        return res - 1

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:

        return len(set(x for i in range(1,len(tiles)+1) for x in itertools.permutations(tiles,i)))
        


class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        
        def freq(tiles):
            d = {}
            for c in tiles:
                if c in d:
                    d[c] += 1
                else:
                    d[c] = 1
            return d
        
        def build(d, s):
            new_d = {}
            for key, value in d.items():
                if key == s:
                    new_d[key] = value - 1
                else:
                    new_d[key] = value
            return new_d
        
        def generate(options):
            sol = []
            for key, value in options.items():
                if value > 0:
                    sol.append(key)
                    fringe = generate(build(options, key))
                    sol += fringe
                    sol += [key + f for f in fringe]
            return sol        
        
        return len(set(generate(freq(tiles))))

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        
        #self.seen=set()
        @lru_cache(None)
        def find(s):
            if len(s)<=1:
                return set([s])
            
            ret=set()
            for i in range(len(s)):
                head=s[i]
                tails=find(s[:i]+s[i+1:])
                ret=ret.union(tails)
                for tail in tails:
                    for j in range(len(tail)+1):
                        temp=tail[:j]+head+tail[j:]
                        ret.add(temp)
            return ret
        res=find(tiles)
        #print(res)
        return len(set(res))
                        
            


from collections import Counter

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        
        c_all, visited = Counter(tiles), set()
        stack = [(x, Counter([x])) for x in c_all]
        
        while stack:
            element, c = stack.pop()
            if element not in visited:
                stack.extend([(element + x, c + Counter([x])) for x in c_all - c])
                visited.add(element)
                
        return len(visited)

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        pos = set()
        def choose(s, n, pref=''):
            if n == 0:
                pos.add(pref)
            
            for i in range(len(s)):
                choose(s[:i] + s[i+1:], n-1, pref + s[i])
        
        for i in range(1, len(tiles)+1):
            choose(tiles, i)
        return len(pos)


class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        words = set()
        curr = ''
        tile_count = {}
        for x in tiles:
            if x not in tile_count:
                tile_count[x] = 0
            tile_count[x] += 1
        
        def walk(curr, tiles, words):
            #print(tiles, curr)
            for tile in tiles:
                if tiles[tile] > 0:
                    temp = curr + tile
                    #print('Temp', temp)
                    temp_tiles = tiles.copy()
                    temp_tiles[tile] -= 1
                    words.add(temp)
                    walk(temp, temp_tiles, words)
        for tile in tile_count:
            walk('', tile_count, words)
        return len(words)

class Solution:
    def __init__(self):
        self.total = 0
        self.string = []
        self.dict_ = {}
        self.arr = []
        self.n = 0
    
    def perm(self):
        if(self.n==len(self.string)):
            #print(string)
            self.total+=1
            #print(self.total)
        
        for i in range(len(self.arr)):
            if(self.arr[i][1]>0):
                self.arr[i][1]-=1
                self.string.append(self.arr[i][0])
                self.perm()
                self.string.pop()
                self.arr[i][1]+=1
    
    
    def numTilePossibilities(self, tiles: str) -> int:
        for string in tiles:
            if string in self.dict_:
                self.dict_[string]+=1
            else:
                self.dict_[string] = 1
                
        for key in self.dict_:
            temp = [key,self.dict_[key]]
            self.arr.append(temp)
                
        #print(self.arr)
        
        for i in range(1,len(tiles)+1):
            self.n = i
            #print(self.n)
            self.perm()
        #self.perm() 
        return self.total
            
            
        


class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        combination_set = self.generateTilePossibilities(tiles)
        return len(combination_set)

    def generateTilePossibilities(self, tiles: str):
        n = len(tiles)
        combination_set = set()
        for index in range(n):
            combination_set.add(tiles[index])
        if n > 1:
            for index in range(n):
                tiles_without_n = tiles[0:index] + tiles[index + 1:]
                additional_combinations = self.generateTilePossibilities(
                    tiles_without_n)
                combination_set.add(tiles_without_n)
                for combination in additional_combinations:
                    combination_set.add(combination)
                    for second_index in range(len(combination)):
                        new_tile_combination = combination[
                            0:second_index] + tiles[index] + combination[
                                second_index:]
                        combination_set.add(new_tile_combination)
        return combination_set


class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        
        
        def count(tiles):
            #print(tiles)
            counter = set()
            if len(tiles) == 1:
                counter.add(tiles)
            elif len(tiles) == 2:
                counter.add(tiles)
                counter.add(tiles[::-1])
                counter.add(tiles[0])
                counter.add(tiles[1])
            else:
                for idx, i in enumerate(tiles):
                    x = count(tiles[:idx] + tiles[idx+1:])
                    extra = set()
                    for j in x:
                        extra.add(tiles[idx] + j)
                        extra.add(j + tiles[idx])
                        for k in range(1, len(j)-1):
                            extra.add(j[:k] + tiles[idx] + j[k+1:])
                    x.update(extra)
                    counter.update(x)
            #print(counter)
            return counter
        
        return len(count(tiles))



class Solution:
    def __init__(self):
        self.seen = set()
        self.result = set()

    def numTilePossibilities(self, tiles: str) -> int:
        self.dfs(tiles, 0, [])
        return len(self.result) - 1

    def dfs(self, string, idx, path):
        
        st = ''.join(path)

        if st not in self.seen:
            self.result.update((''.join(p) for p in permutations(st)))
            self.seen.add(st)
        
        for i in range(idx, len(string)):
            self.dfs(string, i + 1, path + [string[i]])

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        d = {}
        for i in range(len(tiles)):
            if (tiles[i] in d):
                d[tiles[i]] += 1
            else:
                d[tiles[i]] = 1
        def countnum(d):
            if (d == {}):
                return 0
            c = 0
            s = set(d.items())
            for k, v in s:
                d[k] -= 1
                if (d[k] == 0):
                    del(d[k])
                c += 1 + countnum(d)
                if (k in d):
                    d[k] += 1
                else:
                    d[k] = 1
            return c
        return countnum(d)
                
        


class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        res = set()
        def dfs(path, t):
            if path not in res:
                if path:
                    res.add(path)
                for i in range(len(t)):
                    dfs(path+t[i], t[:i] + t[i+1:])
                
        dfs('', tiles)
        return len(res)

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:

        res = set()
        def backtrack(path, curr):
            if path not in res:
                if path:
                    res.add(path)
                for i in range(len(curr)):
                    backtrack(path + curr[i], curr[:i] + curr[i+1:])
        
        backtrack('', tiles)
        return len(res)

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        d=set()
        for i in range(len(tiles)):
            for x in list(permutations(tiles,i+1)):
                d.add(''.join(x))
        print(d)
        return len(d)


class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        result = set()
        maxx = len(tiles)
        def dfs(result,tiles,current_sequence=''):
            result.add(current_sequence)
            for t in tiles:
                tiles_c = tiles.replace(t,'',1)
                dfs(result,tiles_c,current_sequence+t)
        dfs(result,tiles)
        return len(result)-1

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        setter = set()
        res = []
        for r in range(1,len(tiles)+1): 
            res.append(list(itertools.permutations(tiles,r)))
        result = []
        for re in res: 
            result.append(list(set(re)))
        leng = 0 
        for i in result: 
            leng += len(i)
        return leng            


class Solution:
    
    def numTilePossibilities(self, tiles: str) -> int:
        tile_counts = collections.Counter(tiles)
        len_counts  = [1] + [0] * len(tiles)
        
        for tile in tile_counts:
            new_len_counts  = [0] * (len(tiles) + 1)
            num_tiles       = tile_counts[tile]
            
            for num_inserted in range(num_tiles + 1):
                for old_len, old_len_count in enumerate(len_counts):
                    new_len = old_len + num_inserted
                    if new_len > len(tiles):
                        break
                    num_patterns = math.comb(new_len, num_inserted)
                    new_len_counts[new_len] += old_len_count * num_patterns
                    
            len_counts = new_len_counts
        
        return sum(len_counts) - 1


class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        result = set()
        maxx = len(tiles)
        def dfs(result,tiles,current_sequence=''):
            if len(current_sequence) <= maxx and current_sequence!='':
                result.add(current_sequence)
            for t in tiles:
                tiles_c = tiles.replace(t,'',1)
                dfs(result,tiles_c,current_sequence+t)
        dfs(result,tiles)
        return len(result)

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        result = set()
        maxx = len(tiles)
        def dfs(result,tiles,current_sequence=''):
            if current_sequence!='':
                result.add(current_sequence)
            for t in tiles:
                tiles_c = tiles.replace(t,'',1)
                dfs(result,tiles_c,current_sequence+t)
        dfs(result,tiles)
        return len(result)

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        count = {}
        
        for i in tiles:
            if i not in count:
                count[i] = 0
            count[i]+=1
        
        op = set()
        for ch in count:
            tempString = ch
            op.add(tempString)
            count[ch]-=1
            tempCount = count.copy()
            buildString(tempString,tempCount,op)
            count[ch]+=1
            
        return len(op)
            
def buildString(currString,count,op):
    flag = True
    for i in count:
        if count[i]!=0:
            flag = False
            break
    if flag:
        return
    
    for ch in count:
        if count[ch]==0:
            continue
        tempString = currString
        tempString+=ch
        
        op.add(tempString)
        count[ch]-=1
        
        tempCount = count.copy()
        buildString(tempString,tempCount,op)
        count[ch]+=1
        
        
        


class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        def dfs(state):
            res.append(state.copy())
            for i in range(len(state)):
                if state[i]<full_state[i]:
                    state[i] += 1
                    dfs(state)
                    state[i] -= 1
        
        memo = collections.Counter(tiles)
        full_state = list(memo.values())
        state = [0 for _ in range(len(memo))]
        res = []
        dfs(state)
        return len(res)-1

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        res = {}
        def dfs(seq, tiles):
            if seq not in res and seq != '':
                res[seq] = 1
            for i in range(len(tiles)):
                dfs(seq+tiles[i], tiles[:i]+tiles[i+1:])
        dfs('', tiles)
        return len(res)


class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        def dfs(path, t):
            if path:
                result.add(path)
                
            for i in range(len(t)):
                dfs(path + t[i], t[:i]+t[i+1:])
        
        result = set()
        dfs('', tiles)
        return len(result)

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        def backtracking(idx=0,seq='',remaining=tiles):
            for i, tile in enumerate(remaining):
                res.add(seq+tile)
                backtracking(idx+1, seq+tile, remaining[:i]+remaining[i+1:])
                
        res = set()
        backtracking()
        return len(res)

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        def dfs(elements):
            if prev_elements:
                result.add(''.join(prev_elements))
            
            for e in elements:
                next_elements = elements[:]
                next_elements.remove(e)
                
                prev_elements.append(e)
                dfs(next_elements)
                prev_elements.pop()
            
        result = set()
        prev_elements = []
        
        dfs(list(tiles))
        
        return len(result)


class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        seqs = set()
        visits = [False] * len(tiles)

        def dfs(seq: str, depth: int):
            if seq:
                seqs.add(seq)
            if depth == len(tiles) - 1:
                return

            for i in range(len(tiles)):
                if not visits[i]:
                    visits[i] = True
                    dfs(seq + tiles[i], depth + 1)
                    visits[i] = False

        dfs('', -1)
        return len(seqs)

class Solution:
    def get_permute(self, opts, cur_sol):
        for i in range(len(opts)):
            c = opts[i]
            cur_sol.append(c)
            self.solutions.add(''.join(cur_sol))
            opts2 = opts
            opts2 = opts2[:i] + opts2[i+1:]
            self.get_permute(opts2, cur_sol)
            cur_sol.pop()
        
    def numTilePossibilities(self, tiles: str) -> int:
        self.solutions = set()
        self.get_permute(tiles, [])
        return len(self.solutions)

# This is a mathematical problem.
# Get the frequencies of different characters [f_0, f_1, ..., f_n].
# For each possible choice of frequency [i_0, i_1, ..., i_n] (0 <= i_k <= f_k, k = 0, 1, ..., n),
# the number of distinct sequences is (i_0 + i_1 + ... + i_n)! / ( i_0! * i_1! * ... * i_n!).

# To get numbers of occurrences you can just run

#         freq = count.values()
# for this problem you only need to iterate over freq, so you don't even need to convert it to list.
# Kind of depends on your taste, but for calculating digits you have the option of using divmod:

#             for f in freq:
#                 i, mod = divmod(i, f + 1)
#                 digits.append(mod)



import collections, math
class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        freq = collections.Counter(tiles)
        prod = 1
        for f in freq.values():
            prod *= f + 1
        res = 0
        for i in range(1, prod):
            digits = []
            for f in freq.values():
                digits.append(i % (f + 1))
                i = i // (f + 1)
            tmp = math.factorial(sum(digits))
            for d in digits:
                tmp //= math.factorial(d)
            res += tmp
        return res

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        result = set()
        vis = [0]*len(tiles)
        
        def dfs(res,depth):
            if res:
                result.add(res)
            if depth == len(tiles)-1:
                result.add(res)
            
            for i in range(len(tiles)):
                if not vis[i]:
                    vis[i] = 1
                    dfs(res+tiles[i],depth+1)
                    vis[i] = 0
        
        dfs('',-1)
        return len(result)

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        def solve(s,visited):
            seen.add(s)
            if len(s) == len(tiles):return 0
            for i , v in enumerate(tiles):
                if i not in visited:
                    solve(s + v,visited | {i})
            return len(seen)
        seen = set()
        return solve('',set()) - 1


class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        result = set()
        
        def dfs_helper(path, t):
            if path:
                result.add(path)
            for i in range(len(t)):
                dfs_helper(path + t[i], t[:i] + t[i+1:])
          
        dfs_helper('',tiles)
        return len(result)


class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        ans = 0
        s = set()
        def tot(curr, rem):
            nonlocal s    
            if curr[-1]:
                s.add(tuple(curr[-1]))
            for i in range(len(rem)):
                    el = curr[-1]
                    if rem[i] == el:
                        continue
                    tot(curr+[el + [rem[i]]], rem[:i] + rem[i+1:])
        tot([[]], tiles)
        return len(s)

class Solution:
    
    def subsets(self, tiles, buff, buff_index, boolean, s):
        if tuple(buff[:buff_index]) not in s:  
            # print(buff[:buff_index])
            s.add(tuple(buff[:buff_index]))
            self.count += 1
        if len(buff) == buff_index: return  
        
        for i in range(0, len(tiles)):
            if not boolean[i]:
                buff[buff_index] = tiles[i]
                boolean[i] = True
                self.subsets(tiles, buff, buff_index+1, boolean, s)
                boolean[i] = False
                
    def numTilePossibilities(self, tiles: str) -> int:
        self.count = 0
        buff = [None]*len(tiles)
        boolean = [False]*len(tiles)
        s = set()
        self.subsets(tiles, buff, 0, boolean, s)
        return self.count-1
        


class Solution:
    def numTilePossibilities(self, tiles):
        res=set()
        
        def helper(t,curr,k):
            if k==len(curr):
                res.add(curr)
                return # return so that the loop below doesn't continue when you meet the length requirement
            
            for i in range(len(t)):
                # call helper with everything but the current value
                helper(t[:i]+t[i+1:], curr+t[i], k)
                
        # start at size 1 and move until size len(tiles), +1 because range doesn't include the endpoint
        for i in range(1,len(tiles)+1):
            helper(tiles,'',i)
            
        return((len(res)))     


class Solution:

    def make_tile(self, curr, used, letters, size):
        
        if len(curr) == size:
            
            # print(curr)
            
            self.res += 1
            
            return
        
        i = 0
            
        while i < len(letters):
            
            if i not in used:
                
                used.add(i)
            
                curr.append(letters[i])

                self.make_tile(curr, used, letters, size)

                curr.pop(-1)

                used.remove(i)
                
                while i + 1 < len(letters) and letters[i] == letters[i + 1]:

                    i += 1
                
            i += 1
            
    def numTilePossibilities(self, tiles: str) -> int:
        
        self.res = 0
        
        letters = sorted(tiles)
        
        for size in range(1, len(tiles) + 1):
            
            self.make_tile([], set(), letters, size)
            
        return self.res

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        def next_permutation(a):
            for i in range(len(a) - 1, 0, -1):
                if a[i] > a[i - 1]:
                    ps = i
                    for j in range(i + 1, len(a)):
                        if a[j] > a[i - 1] and a[ps] > a[j]:
                            ps = j
                    a[ps], a[i - 1] = a[i - 1], a[ps]
                    p1 = i
                    p2 = len(a) - 1
                    while p1 < p2:
                        a[p1], a[p2] = a[p2], a[p1]
                        p1 += 1
                        p2 -= 1
                    return True
            return False
                    
        n = 1
        for i in range(1, len(tiles) + 1):
            n *= i
        a = set()
        perm = []
        for i in range(len(tiles)):
            perm.append(i)
        for _ in range(n):
            cur = ''
            for i in range(len(tiles)):
                cur += tiles[perm[i]]
            for i in range(len(tiles)):
                a.add(cur[:i + 1])
            next_permutation(perm)
        return len(a)

from collections import Counter

class Solution:
    def __init__(self):
        self.sum_ = 0
        
    def recurse_count(self, letter_count):
        if len(letter_count)==0:
            return            
        for letter in letter_count:
            self.recurse_count(letter_count - Counter(letter))
            self.sum_ += 1
        return
    
    def numTilePossibilities(self, tiles: str) -> int:
        letter_count = Counter(tiles)
        self.recurse_count(letter_count)
        return self.sum_            

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:

        
        def recur(tiles):
            if not tiles: return set()
            ans = set()
            temp = ''
            while tiles:
                v = tiles[0]
                ans.add(v)
                new = recur(temp+tiles[1:])
                ans.update(new)
                for k in new: ans.add(v+k)
                temp+=tiles[0]
                tiles = tiles[1:]
            return ans
            
        ans = recur(tiles)
        # print(ans)
        return len(ans)

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        #sequence can be of length 0 to len(tiles)
        result = set()   
        def backtrack(left_tiles, curr_seq):#k is our desired length 
            if len(curr_seq) == k:#reached our desired length 
                result.add(''.join(curr_seq))
                return 
            else:
                for i in range(len(left_tiles)):
                    curr_seq.append(left_tiles[i])
                    backtrack(left_tiles[:i] + left_tiles[i+1:], curr_seq)
                    curr_seq.pop()
                    
                    
        for k in range(1, len(tiles)+1):
            backtrack(tiles, [])
        return len(result)

                    

                


class Solution:
    def numTilePossibilities(self, tiles: str) -> int:

        
        def recur(tiles):
            if not tiles: return set()
            ans = set()
            for i,v in enumerate(tiles):
                ans.add(v)
                new = recur(tiles[:i]+tiles[i+1:])
                ans.update(new)
                for k in new: ans.add(v+k)
            return ans
            
        ans = recur(tiles)
        # print(ans)
        return len(ans)

class Solution:
    def counts(self, collect):
        answer = 1
        for char in collect:
            if collect[char]:
                answer += self.counts(collect - collections.Counter(char))
        return answer
    def numTilePossibilities(self, c):
        return self.counts(collections.Counter(c)) - 1    

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        tiles = ''.join(sorted(tiles))
        memo = {}
        def helper(s, k):
            if (s, k) not in memo:
                if k == 0:
                    memo[(s,k)] = 1
                else:
                    last, ans = '', 0
                    for i in range(len(s)):
                        if s[i] != last:
                            last = s[i]
                            ans += helper(s[:i]+s[i+1:], k-1)
                    memo[(s,k)] = ans
            return memo[(s,k)]

        ret = 0
        for k in range(1, len(tiles)+1):
            ret += helper(tiles, k)
        return ret

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        def perm(k, a):
            if k == 0:
                return []
            elif k == 1:
                return [x for x in a]
            else:
                return [a[i] + y for i in range(len(a)) for y in perm(k-1, a[:i] + a[i+1:])]
        
        out = set()
        for i in range(1, len(tiles)+1):
            for x in perm(i, tiles):
                out.add(x)
        
        return len(out)
    

# complexity: N = len(t), N*N!
# space complexity: O(N!)


from collections import Counter

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:

        counter = Counter(tiles)
        
        def dfs(counter):
            result = len(counter)
            print(result)
            
            for character in counter:
                temp = counter.copy()
                if temp[character] == 1:
                    del temp[character]
                else:
                    temp[character] -= 1
                
                result += dfs(temp)
            
            return result
        
        result = dfs(counter)
        
        return result
            
            
        
        
        


class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        
        output = set()
        
        def helper(result, options):
            if not options:
                return
            for idx, o in enumerate(options):
                tmp = options[:]
                tmp.pop(idx)
                output.add(''.join(result + [o]))
                helper(result + [o], tmp)
            
        helper([], list(tiles))
        
        return len(output)

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        def helper(curr, tiles):
            for i in range(len(tiles)):
                curr.append(tiles[i])
                pos.add(str(curr))
                c = tiles.copy()
                c.pop(i)
                helper(curr.copy(), c)
                curr.pop()
            
        tiles = list(tiles)
        pos = set()
                
        helper([], tiles)
        return len(pos)
        
                
            
            


class Solution:
    def poss(self, tiles:str) -> set:
        if len(tiles) == 1:
            return set([tiles[0]])
        output = set()
        for i in range(len(tiles)):
            elem = tiles[i]
            res = self.poss(tiles[:i]+tiles[i+1:])
            output = output.union(res)
            for elem in res:
                output.add(tiles[i]+elem)
        return output
            
    
    def numTilePossibilities(self, tiles: str) -> int:
        if len(tiles) == 0:
            return 0
        return len(self.poss(tiles))

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        seen = set()
        ans = set()
        
        
        
        def backtrack(tiles,seen,curr):
            if curr != '' and curr not in ans:
                ans.add(curr)
                
            for i in range(len(tiles)):
                if i not in seen:
                    seen.add(i)
                    backtrack(tiles,seen,curr+tiles[i])
                    seen.remove(i)

        backtrack(tiles,seen,'')
        return len(ans)

from itertools import permutations


class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        total = 0
        for size in range(1, len(tiles) + 1):
            total += len(set(permutations(tiles, size)))
            
        return total


class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        
        def backtrack(i, c):
            if i == n:
                return
            
            for k in c:
                if c[k] > 0:
                    self.ans += 1
                    backtrack(i + 1, c - Counter(k))
            
                    
            
            
        n = len(tiles)
        counter = Counter(tiles)
        self.ans = 0
        backtrack(0, counter)
        return self.ans


class Solution:
    def __init__(self):
        self.res = set()
        
    def backtrack(self,tiles,curr,indices):
        
        for i in range(len(tiles)):
            if i not in set(indices):
                curr+=tiles[i]
                indices.append(i)
                self.res.add(curr)
                
                if len(curr)<len(tiles):
                    self.backtrack(tiles,curr,indices)
                curr = curr[:-1]
                indices.pop()
                
                
        
        
    def numTilePossibilities(self, tiles: str) -> int:
        
        self.backtrack(tiles,'',[])
        
        return len(self.res)

def possible(tiles):
    variants = set()
    if len(tiles) == 1:
        variants.add(tiles[0])
    else:
        for i in range(len(tiles)):
            t = possible(tiles[:i]+tiles[i+1:])
            variants.update(t)
            for j in t:
                variants.add(tiles[i]+j)
    return variants
    

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        return len(possible(tiles))
        
            


from itertools import combinations as C
class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        num = 0
        for i in range(1, len(tiles)+1):
            l = set(permutations(tiles, i))
            num += len(l)
        return num

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        if len(tiles) < 2:
            return len(tiles)
        nodes = []
        for letter in tiles:
            nodes.append(Node(letter))
        for node in nodes:
            for other_node in nodes:
                if node != other_node:
                    node.edges.append(other_node)
        paths = set()
        seen = set()
        for node in nodes:
            self.backtrack(node, seen, node.char, paths)
        print(paths)
        return len(paths)
        
    def backtrack(self, node, seen: set, path: str, paths: set):
        if node in seen:
            return
        path += node.char
        if path and path not in paths:
            paths.add(path)
        for neighbor in node.edges:
            seen.add(node)
            self.backtrack(neighbor, seen, path, paths)
            seen.remove(node)
        
class Node:
    def __init__(self, char: str):
        self.char = char
        self.edges = []

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        
        possibilities = set()
        
        def swap(arr, l, r):
            if l == r: return
            arr[l], arr[r] = arr[r], arr[l]
        
        def add_permutation(arr):
            nonlocal possibilities
            
            for i in range(len(arr)):
                possibilities.add(''.join(arr[:i+1]))
        
        def build_permutations(arr, start = 0):
            
            if start >= len(arr):
                add_permutation(arr)
                return
            
            for i in range(start, len(arr)):
                swap(arr, i, start)
                build_permutations(arr, start + 1)
                swap(arr, i, start)
        
        build_permutations(list(tiles))
        return len(possibilities)

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        if len(tiles) < 2:
            return len(tiles)
        nodes = []
        for letter in tiles:
            nodes.append(Node(letter))
        for node in nodes:
            for other_node in nodes:
                if node != other_node:
                    node.edges.append(other_node)
        paths = set()
        seen = set()
        for node in nodes:
            self.backtrack(node, seen, node.char, paths)
        return len(paths)
        
    def backtrack(self, node, seen: set, path: str, paths: set):
        if node in seen:
            return
        path += node.char
        if path and path not in paths:
            paths.add(path)
        for neighbor in node.edges:
            seen.add(node)
            self.backtrack(neighbor, seen, path, paths)
            seen.remove(node)
        
class Node:
    def __init__(self, char: str):
        self.char = char
        self.edges = []

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        count=0
        for i in range(1,len(tiles)+1):
            count+=len(set(permutations(tiles,i)))
        return count

class Solution:
    result = 0
    
    def numTilePossibilities(self, tiles: str) -> int:
        counter = Counter(tiles)
        self.dfs(counter, [])
        return self.result
        
    def dfs(self, counter, curr):
        if curr:
            self.result += 1
        for x in counter:
            curr1 = curr.copy()
            counter1 = counter.copy()
            curr1.append(x)
            counter1[x] -= 1
            if counter1[x] == 0:
                del counter1[x]
            self.dfs(counter1, curr1)    


class Solution:
    def numTilePossibilities(self, s: str) -> int:
        ans, C = 0, Counter(s)                
        def dfs(C, cur):
            nonlocal ans
            if cur: ans += 1
            if not C: return
            C1 = C.copy()
            for x in C:
                cur.append(x); C1[x] -= 1
                if C1[x] == 0: del C1[x]
                dfs(C1, cur)
                cur.pop(); C1[x] += 1        
        dfs(C, cur=[])
        return ans

class Solution:
    memos = dict()
    
    def numTilePossibilities(self, tiles: str) -> int:
        tiles = ''.join(sorted(tiles))
        uniques = self.step(tiles)
        return len(uniques) - 1
    
    def step(self, tiles: str) -> set:
        if len(tiles) == 0:
            return {''}
        if tiles not in self.memos:
            uniques = set()
            for i in range(len(tiles)):
                c = tiles[i]
                substr = tiles[:i] + tiles[i + 1:]
                substrs_set = self.step(substr)
                for substr in substrs_set:
                    uniques.add(substr)
                    for j in range(len(substr) + 1):
                        new_str = substr[:j] + c + substr[j:]
                        uniques.add(new_str)
            self.memos[tiles] = uniques
        return self.memos[tiles]


class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        res = set()

        def seq(s, l):
            if len(l) == 0:
                res.add(s)
                return
            seq(s, l[1 : ])
            for i in range(len(l)):
                seq(s + l[i], l[ : i] + l[i + 1 : ])

        seq('', list(tiles))

        return len(res) - 1

from collections import Counter

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        
        def permutation(num, tiles_counter):
            if num == 1:
                return len(list(tiles_counter))
            rs = 0
            for c in +tiles_counter:
                rs += permutation(num-1, tiles_counter - Counter({c:1}))
            return rs
        
        
        total = 0
        for i in range(1, len(tiles) + 1):
            total += permutation(i, Counter(tiles))
            
            
    
        return total