# Leetcode: Letter Tile Possibilities

Letter Tile Possibilities

Similar Problems:

You have a set of 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.

Example 1:

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

Example 2:

```Input: "AAABBC"
Output: 188
```

Note:

1. 1 <= tiles.length <= 7
2. tiles consists of uppercase English letters.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

• Solution:
```// Blog link: https://code.dennyzhang.com/letter-tile-possibilities
// Basic Ideas: Permutation with duplicate elements
//
// Complexity: Time ?, Space ?
import "sort"
func dfs(chars []int, l []int, items []byte, pos int) int {
res := 0
// Combination with current setup
count, val := 0, 1
for _, v := range chars {
if v != 0 {
count += v
val *= l[v]
}
}
if count != 0 {
res += l[count]/val
}
for i:=pos; i<len(items); i++ {
if (i>pos) && (items[i-1] == items[i]) { continue }
j := items[i]-'A'
chars[j]++
res += dfs(chars, l, items, i+1)
chars[j]--
}
return res
}

func numTilePossibilities(tiles string) int {
l := []int{1, 1, 2, 6, 24, 120, 720, 5040}
items := []byte(tiles)
sort.Slice(items, func(i, j int) bool {
return items[i] < items[j]
})
chars := make([]int, 26)
return dfs(chars, l, items, 0)
}
```

Share It, If You Like It.