1079. Letter Tile Possibilities

MediumView on LeetCode

Hash Table String Dynamic Programming Backtracking Counting

Time: O(n!)

Space: O(n)

Intuition

Count all distinct non-empty sequences using backtracking. Character frequency map to handle duplicates.

Algorithm

1Count char frequencies.
2Backtrack: for each char with freq > 0: use it (freq--), increment count, recurse, restore.

Common Pitfalls

•Each recursive call represents one valid sequence (non-empty). Count all calls.

1079.cs

// Approach: Frequency-array DFS; for each non-zero character, decrement its count, recurse, and accumulate all sub-sequence counts.
// Time: O(n!) Space: O(n)

public class Solution
{
    public int NumTilePossibilities(string tiles)
    {
        int[] count = new int[26];

        foreach (char t in tiles)
            count[t - 'A']++;

        return Dfs(count);
    }

    private int Dfs(int[] count)
    {
        int possibleSequences = 0;

        for (int i = 0; i < count.Length; i++)
        {
            if (count[i] == 0)
                continue;
            // Put c in the current position. We only care about the number of
            // possible sequences of letters but don't care about the actual
            // combination.
            count[i]--;
            possibleSequences += 1 + Dfs(count);
            count[i]++;
        }

        return possibleSequences;
    }
}

Was this solution helpful?