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: MEDIUM
Tags: String algorithms

Data structures

Mathematics

Complete search
Skill types: Data structures

Complete search

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:

		@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)
		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):
			for tile in tiles:
				if tiles[tile] > 0:
					temp = curr + tile
					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):
			self.total += 1
		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)
		for i in range(1, len(tiles) + 1):
			self.n = i
			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):
			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)
			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:
		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 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)


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:
			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
			for i in range(len(t)):
				helper(t[:i] + t[i + 1:], curr + t[i], k)
		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:
			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)
		return len(ans)


class Solution:

	def numTilePossibilities(self, tiles: str) -> int:
		result = set()

		def backtrack(left_tiles, curr_seq):
			if len(curr_seq) == k:
				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)
		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)


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:
		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