Today’s problem

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

Intuition

In this question, we want to know how many different tiles we can generate.

Approach

Therefore, we can use backtracking to enumerate all the solutions.

Complexity

  • Time complexity: $O(2^N)$, N is the length of the sequence.

  • Space complexity: $O(N)$, N is the length of the sequence.

Code

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        counter = defaultdict(int)
        for ch in tiles:
            counter[ch] += 1

        def dfs(counter):
            total = 0
            for ch in counter:
                if counter[ch] == 0:
                    continue
                # Choose character
                total += 1
                counter[ch] -= 1
                total += dfs(counter)
                counter[ch] += 1  # backtracking
            return total
        return dfs(counter)