Letter Tile Possibilities

Problem#

Given a string of uppercase letters (multiset of tiles), return the number of distinct non-empty sequences you can form by ordering some subset of them.

Examples#

"AAB" → 8 ("A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA")

Constraints#

1 <= s.length <= 7.

Hints#

Hint 1

Frequency map; DFS over the 26 letters at each step. Each pick contributes 1 + sub-count.

Approach#

Frequency vector of length 26. DFS: at each call, for each letter with count > 0, “place it” (decrement), count this as 1 sequence + the count from the recursive subtree.

Solution#

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

func numTilePossibilities(tiles string) int {
    cnt := [26]int{}
    for _, c := range tiles {
        cnt[c-'A']++
    }
    var dfs func() int
    dfs = func() int {
        sum := 0
        for i := 0; i < 26; i++ {
            if cnt[i] == 0 {
                continue
            }
            cnt[i]--
            sum += 1 + dfs()
            cnt[i]++
        }
        return sum
    }
    return dfs()
}

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        cnt = [0] * 26
        for c in tiles:
            cnt[ord(c) - ord('A')] += 1

        def dfs() -> int:
            total = 0
            for i in range(26):
                if cnt[i] == 0:
                    continue
                cnt[i] -= 1
                total += 1 + dfs()
                cnt[i] += 1
            return total

        return dfs()

function numTilePossibilities(tiles) {
    const cnt = new Array(26).fill(0);
    for (const c of tiles) cnt[c.charCodeAt(0) - 65]++;
    const dfs = () => {
        let sum = 0;
        for (let i = 0; i < 26; i++) {
            if (cnt[i] === 0) continue;
            cnt[i]--;
            sum += 1 + dfs();
            cnt[i]++;
        }
        return sum;
    };
    return dfs();
}

class Solution {
    private int[] cnt;

    public int numTilePossibilities(String tiles) {
        cnt = new int[26];
        for (int i = 0; i < tiles.length(); i++) cnt[tiles.charAt(i) - 'A']++;
        return dfs();
    }

    private int dfs() {
        int sum = 0;
        for (int i = 0; i < 26; i++) {
            if (cnt[i] == 0) continue;
            cnt[i]--;
            sum += 1 + dfs();
            cnt[i]++;
        }
        return sum;
    }
}

function numTilePossibilities(tiles: string): number {
    const cnt: number[] = new Array(26).fill(0);
    for (const c of tiles) cnt[c.charCodeAt(0) - 65]++;
    const dfs = (): number => {
        let sum = 0;
        for (let i = 0; i < 26; i++) {
            if (cnt[i] === 0) continue;
            cnt[i]--;
            sum += 1 + dfs();
            cnt[i]++;
        }
        return sum;
    };
    return dfs();
}

Editorial#

Counting on the multiset side avoids enumerating sequences as strings. The DFS implicitly dedups: identical tiles are picked from the same bucket, never producing duplicate sequences. Each recursive call adds one for the new pick and recurses for extensions.

Complexity#

Time: O(n!) in the worst (all distinct) case.
Space: O(|Σ|).

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#