# Letter Tile Possibilities
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/letter-tile-possibilities)
Canonical: https://scaleengineer.com/dsa/problems/letter-tile-possibilities
**Patterns:** [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking), [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Hash Table, String
---
## 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 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.

# Approaches
## Brute-force Backtracking with a Set
This approach directly simulates the problem by generating all possible non-empty sequences of letters and then counting how many unique sequences were found. It uses a backtracking algorithm to explore every permutation of every possible length. A `HashSet` is used to automatically handle uniqueness; by adding every generated sequence to the set, duplicates are discarded. The final answer is simply the size of the set.
**Time:** O(n * Σ_{k=1 to n} P(n, k)) where P(n, k) is the number of k-permutations of n. The recursion tree has Σ P(n, k) nodes, and in each node, we perform operations (looping, string manipulation) that can take up to O(n) time. Sorting the initial array takes O(n log n). · **Space:** O(n * Σ_{k=1 to n} P(n, k)) where n is the length of `tiles`. The space is dominated by the `HashSet` which stores all unique sequences. The recursion stack depth adds an additional O(n).
**Pros:** The logic is straightforward and directly models the process of building and collecting all possible sequences.; It's relatively easy to implement for those familiar with basic backtracking.
**Cons:** Highly inefficient in terms of both time and space complexity.; Generates and stores all possible sequences in memory, which is unnecessary as the problem only asks for the count.; The memory usage can be substantial due to the `HashSet` storing potentially many long strings.
### Explanation
The core of this method is a recursive backtracking function. To handle duplicate letters in the input `tiles` (like in "AAB"), we first sort the `tiles` string. This groups identical letters together, making them easier to manage.

The backtracking function, let's call it `dfs`, builds sequences character by character. It uses a boolean `visited` array to keep track of which tiles have been used in the current path. In each recursive step, it iterates through the tiles. If a tile hasn't been visited, it appends it to the current sequence, adds this new sequence to a `HashSet`, marks the tile as visited, and then calls itself to extend the sequence further.

The key to handling duplicates lies in a specific condition: if the current tile is identical to the previous one and the previous one was *not* used in the current path (i.e., we have backtracked past it), we skip the current tile. This pruning strategy prevents the algorithm from starting new paths with the second 'A' that are identical to paths already generated with the first 'A', thus avoiding duplicate permutations.

After a recursive call returns, the function backtracks by undoing its last choice—removing the character from the sequence and un-marking it as visited. This allows the exploration of other possibilities. The total count is the final size of the `HashSet`.

```java
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int numTilePossibilities(String tiles) {
        char[] chars = tiles.toCharArray();
        Arrays.sort(chars);
        Set<String> resultSet = new HashSet<>();
        boolean[] visited = new boolean[chars.length];
        dfs(new StringBuilder(), chars, visited, resultSet);
        return resultSet.size();
    }

    private void dfs(StringBuilder currentPath, char[] tiles, boolean[] visited, Set<String> resultSet) {
        for (int i = 0; i < tiles.length; i++) {
            if (visited[i]) {
                continue;
            }
            // This is the key condition to avoid duplicate permutations.
            // If the current character is the same as the previous one,
            // and the previous one has not been picked in this path,
            // skip the current character to avoid redundant computations.
            if (i > 0 && tiles[i] == tiles[i - 1] && !visited[i - 1]) {
                continue;
            }

            visited[i] = true;
            currentPath.append(tiles[i]);
            
            resultSet.add(currentPath.toString());
            dfs(currentPath, tiles, visited, resultSet);
            
            // Backtrack
            currentPath.deleteCharAt(currentPath.length() - 1);
            visited[i] = false;
        }
    }
}
```
### Algorithm
*   Convert the input `tiles` string to a character array and sort it. This helps in handling duplicate characters systematically.
*   Initialize an empty `HashSet<String>` to store the unique sequences found.
*   Initialize a boolean array `visited` of the same size as `tiles`, with all values set to `false`, to keep track of which tile indices have been used in the current sequence.
*   Define a recursive helper function, let's call it `dfs`, that builds the sequences.
*   The `dfs` function iterates through the sorted character array. For each character:
    *   It checks if the character at the current index has already been visited. If so, it skips to the next one.
    *   To avoid generating duplicate permutations (e.g., from "AAB"), it includes a crucial check: if the current character is the same as the previous one (`tiles[i] == tiles[i-1]`) and the previous one has *not* been visited (`!visited[i-1]`), it skips the current character. This ensures that for a group of identical characters, they are always picked in order.
    *   If the character can be used, it's appended to the current sequence being built (e.g., a `StringBuilder`).
    *   The newly formed sequence is added to the `HashSet`.
    *   The character's index is marked as visited.
    *   A recursive call is made to `dfs` to continue building longer sequences.
    *   After the recursive call returns (backtracking), the last character is removed from the sequence builder, and the visited status is reset to `false`.
*   The initial call is made to this `dfs` function.
*   Finally, the size of the `HashSet` is returned, which represents the total number of unique non-empty sequences.

## Backtracking with Frequency Count
This optimized approach avoids the overhead of generating and storing the actual string sequences. Instead, it focuses on counting the possibilities directly. The core idea is that the number of unique sequences depends only on the counts of each available character, not their original positions. We use a frequency map (e.g., an array of size 26) to store the counts of each letter in the `tiles` string. A recursive backtracking function then explores the combinations of these characters, summing up the possibilities at each step without building any strings.
**Time:** The time complexity is difficult to express with a simple formula but is significantly faster than the brute-force approach. It's related to the number of nodes in the decision tree, which is based on the counts of characters, not raw permutations. Given n <= 7, this approach is very fast. · **Space:** O(n), where n is the length of `tiles`. The space is dominated by the depth of the recursion stack, which can go up to n. The frequency map itself takes constant O(1) space (size 26).
**Pros:** Extremely efficient in both time and space.; Avoids expensive string manipulations and the need for a large data structure like a `HashSet` to store results.; Directly calculates the required count, which is more aligned with the problem statement.
**Cons:** The recursive logic, while efficient, might be slightly less intuitive to grasp compared to the direct generation of sequences.
### Explanation
This method transforms the problem from generating permutations of tiles to counting combinations of character frequencies. 

1.  **Frequency Count**: We begin by iterating through the `tiles` string once to populate a frequency array, say `counts`, of size 26. For `tiles = "AAB"`, this array would be `[2, 1, 0, ..., 0]`, indicating two 'A's and one 'B'.

2.  **Recursive Counting**: We define a recursive function, `dfs(counts)`, that calculates the number of unique sequences that can be formed from the available characters represented by the `counts` array. 

Inside `dfs`, we loop through our `counts` array. If `counts[i]` for a character `i` is positive, we know we can form at least one new sequence starting with this character. So, we increment our result counter. Then, to find all sequences that *extend* this one, we decrement `counts[i]` (as if we've used one instance of that character) and make a recursive call `dfs(counts)`. The result of this call is the number of ways to complete the sequence, which we add to our total. 

3.  **Backtracking**: After the recursive call returns, we must restore the state by incrementing `counts[i]` back. This is the backtracking step, ensuring that the character is available again for other recursive paths (e.g., for sequences that don't start with this character).

The final result is the sum of possibilities explored in the initial `dfs` call. This method is highly efficient because the state of the recursion is just the small `counts` array, and we never perform costly string operations or store large collections.

```java
class Solution {
    public int numTilePossibilities(String tiles) {
        int[] counts = new int[26];
        for (char c : tiles.toCharArray()) {
            counts[c - 'A']++;
        }
        return dfs(counts);
    }

    private int dfs(int[] counts) {
        int sum = 0;
        for (int i = 0; i < 26; i++) {
            if (counts[i] == 0) {
                continue;
            }
            // Count the new sequence formed by picking this character.
            sum++;
            
            // Use one character.
            counts[i]--;
            
            // Recursively count sequences that can be formed with the rest.
            sum += dfs(counts);
            
            // Backtrack to restore the count for other possibilities.
            counts[i]++;
        }
        return sum;
    }
}
```
### Algorithm
*   First, create a frequency map of the characters in the input `tiles` string. An integer array of size 26 is suitable for this, where `counts[0]` stores the count of 'A', `counts[1]` for 'B', and so on.
*   Define a recursive helper function, `dfs(counts)`, that calculates and returns the number of unique sequences possible with the given character counts.
*   Inside the `dfs` function, initialize a local counter `sum` to 0.
*   Iterate through the frequency map from `i = 0` to `25`.
*   For each index `i`, if `counts[i]` is greater than 0, it means the character corresponding to `i` is available.
    *   Increment `sum`. This counts the single-character sequence formed by this character.
    *   Decrement `counts[i]` to signify that one instance of this character has been used.
    *   Make a recursive call `dfs(counts)` to find all sequences that can be formed by appending to the character just chosen. Add the returned value to `sum`.
    *   Backtrack by incrementing `counts[i]` back to its previous value. This restores the state for exploring other possibilities (e.g., sequences starting with a different character).
*   The `dfs` function returns the total `sum`.
*   The final answer is the result of the initial call to `dfs` with the frequency map of the original `tiles` string.

# Solutions
### Java

```java
class Solution {
public
  int numTilePossibilities(String tiles) {
    int[] cnt = new int[26];
    for (char c : tiles.toCharArray()) {
      ++cnt[c - 'A'];
    }
    return dfs(cnt);
  }
private
  int dfs(int[] cnt) {
    int res = 0;
    for (int i = 0; i < cnt.length; ++i) {
      if (cnt[i] > 0) {
        ++res;
        --cnt[i];
        res += dfs(cnt);
        ++cnt[i];
      }
    }
    return res;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int numTilePossibilities(string tiles) {
    int cnt[26]{};
    for (char c : tiles) {
      ++cnt[c - 'A'];
    }
    function<int(int *cnt)> dfs = [&](int *cnt) -> int {
      int res = 0;
      for (int i = 0; i < 26; ++i) {
        if (cnt[i] > 0) {
          ++res;
          --cnt[i];
          res += dfs(cnt);
          ++cnt[i];
        }
      }
      return res;
    };
    return dfs(cnt);
  }
};

```

### Python

```python
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)

```