← Back to Index

📚 Letter Tile Possibilities – Java Cheat Sheet

📌 What Is It?

The Letter Tile Possibilities problem involves finding all possible sequences of letters that can be formed using the given tiles. Each tile can be used only once per sequence, and the order of tiles matters.

🧱 Pattern Template

Recursive Backtracking with Visited Array

class Solution {
    public int numTilePossibilities(String tiles) {
        char[] chars = tiles.toCharArray();
        Arrays.sort(chars); // Sort to handle duplicates
        boolean[] visited = new boolean[chars.length];
        return backtrack(chars, visited);
    }

    private int backtrack(char[] chars, boolean[] visited) {
        int count = 0;
        for (int i = 0; i < chars.length; i++) {
            if (visited[i] || (i > 0 && chars[i] == chars[i - 1] && !visited[i - 1])) {
                continue; // Skip duplicates
            }
            visited[i] = true;
            count += 1 + backtrack(chars, visited); // Count current sequence and recurse
            visited[i] = false; // Backtrack
        }
        return count;
    }
}

▶️ View Animation

📊 Time Complexity

• Time Complexity: O(n!), where n is the number of tiles. This accounts for all permutations of the tiles.
• Space Complexity: O(n), for the recursion stack and visited array.

✅ Use Cases

• Generating all possible sequences of letters from a set of tiles.
• Counting unique permutations of a string with duplicate characters.

📘 Common LeetCode Problems

• 1079. Letter Tile Possibilities [Medium] Backtracking

🧪 Example

Input: tiles = "AAB"
Output: 8

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

💡 Pro Tips

• Sort the tiles to handle duplicates efficiently.
• Use a visited array to track which tiles have been used in the current sequence.
• Skip duplicate tiles by checking if the current tile is the same as the previous one and the previous tile has not been visited.