Letter Tile Possibilities — LeetCode 1079 Python Solution

The problem

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

Input

tiles = "AAB"

Output

8

Explanation

The possible sequences are "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA".

Python solution

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        def dfs(cnt: Counter) -> int:
            ans = 0
            for i, x in cnt.items():
                if x > 0:
                    ans += 1
                    cnt[i] -= 1
                    ans += dfs(cnt)
                    cnt[i] += 1
            return ans

        cnt = Counter(tiles)
        return dfs(cnt)

Complexity

Pattern: Backtracking

Build candidates one choice at a time and abandon a branch the moment it cannot work. LeetCode 1079. Letter Tile Possibilities is filed here because LeetCode tags it Backtracking, which is the vocabulary this hub collects.

The backtracking guide has the Python template for the pattern and the 105 LeetCode problems that use it.

Related problems