Permutation with no Repetition

This is a classic problem with a well-established technique for solving it. Comes from Leetcode:

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

You have a set of 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.

Example 1:
Input: "AAB"
Output: 8
Explanation: The possible sequences are "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA".
Example 2:
Input: "AAABBC"
Output: 188

Note:
  1. 1 <= tiles.length <= 7
  2. tiles consists of uppercase English letters.
The solution (or better, one of the solutions) is as follows:
 - Do a standard DFS using the "output position" to control the recursion
 - Have a global hash table tracking the index that has already been used
 - Have a local hash table tracking the character that has already been used
 - That's all

Code's below. Cheers, ACC.


public class Solution
{
    public int NumTilePossibilities(string tiles)
    {
        int num = 0;
        NumTilePossibilities(tiles, 0, new Hashtable(), ref num);
        return num;
    }

    private void NumTilePossibilities(string tiles,
                                        int currentPosition,
                                        Hashtable indexUsed,
                                        ref int num)
    {
        if (currentPosition >= tiles.Length)
        {
            return;
        }

        Hashtable charUsed = new Hashtable();
        for (int i = 0; i < tiles.Length; i++)
        {
            if (!indexUsed.ContainsKey(i) && !charUsed.ContainsKey(tiles[i]))
            {
                num++;
                indexUsed.Add(i, true);
                charUsed.Add(tiles[i], true);
                NumTilePossibilities(tiles, currentPosition + 1, indexUsed, ref num);
                if (indexUsed.ContainsKey(i)) indexUsed.Remove(i);
            }
        }
    }
}

Comments

  1. Very nice! You can significantly speed this up by using a 26 element array of booleans instead of Hashtables for indexUsed and charUsed. I have decided to store counts of characters and at each iteration using one of the available ones:

    class Solution {
    private:
    static const int ALPHABET_SIZE = 26;
    using Counts = array;
    int explore(Counts& counts) {
    int ways = 0;
    for (int i = 0; i < ALPHABET_SIZE; ++i) {
    if (counts[i] < 1) continue;
    counts[i] -= 1;
    ways += 1 + explore(counts);
    counts[i] += 1;
    }
    return ways;
    }
    public:
    int numTilePossibilities(string tiles) {
    Counts counts {0};
    for (char ch : tiles) counts[ch - 'A'] += 1;
    return explore(counts);
    }
    };

    ReplyDelete

Post a Comment

Popular posts from this blog

Golang vs. C#: performance characteristics (simple case study)

Claude vs ChatGPT: A Coder's Perspective on LLM Performance

ProjectEuler Problem 719 (some hints, but no spoilers)