Find the total no. of strings ( len n ) possible given a set of sets of letters such that no two letter from a single set should be in that string

Question

This was an algorithm problem but I am having problems in formulating it.

I have a certain approach but I do not know how to fully execute:

Given

• 26 letters in total
• All possible strings of length n

Example

Find all possible strings of length 5 such that given [{a, b, c}, {d, g, h}], no two letters from each set can occur in that string:

• 'a' and 'd' can occur any number of times in the string, as well as 'a' and 'g'.
• no single instance of 'a' and 'b' occurring or 'b' and 'c' or 'a', 'b' and 'c' ( basically any pair )
• No two sets will have any characters in common such as [{a, b, c}, {d, g, h}, {c, l, f}] not allowed.

My naive approach

• Find all possible strings of length n consisting of characters other than the ones mentioned in the set of sets.
• Take a single set:
  • Take 1 character from a set.
    • Find the characters that are valid with this character and count the possible strings of length n.

But this does not take care of repetitions I think. So is there some other way or do I need to refine more?

Answer 1

Let $n$ be the desired length of the strings to build. Then, let $S_1, S_2, \ldots, S_k$ be the sets constraining the solution. We need to choose a total of $n$ letters, by choosing zero or one letter from each set, and possibly repeating the chosen letter. Then, we need to count all the possible ways of rearranging said choices. This means that for each set $S_i$, we have three choices: how many times we will use a letter from that set, which of the $|S_i|$ letters will it be, and where in the string are those letter going to appear.

Assume we will use a letter from $S_1$ exactly $\ell$ times. We have $|S_1|$ choices for said letter, ${n \choose \ell}$ choices for where to put the $\ell$ ocurrences, and then we need to decide what to do with the remaining $n-\ell$ positions to fill, now without having $S_1$. This is hinting dynamic programming! Let $f(i, m)$ be the number of words of length $m$ you can make by using sets $S_i$ through $S_k$. This means the final answer will be $f(1, n)$.

Now, we can use the previous consideration to define a recursive equation for $f$. As we want all possible values of $\ell$, the number of occurrences for a given set, we can just sum over them.

$$ f(i, m) = f(i+1, m) + |S_i|{\sum_{\ell = 1}^m}\binom{m}{\ell}f(i+1, m-\ell) $$

with the base cases being $f(i, 0) = 1$ for all $i$, and $f(k, j) = |S_k|$ for each $1 \leq j \leq m$. Note that $f(i+1, m)$ appears in the sum as we can choose not to use said set at all.

By implementing this recursive equation as a DP you get an algorithm :), maybe there is something even more efficient, but I can't think of anything right now.