The problem is NP-hard already for $\Sigma = \{a, b\}$. (Of course, it is in PTIME if $|\Sigma| = 1$.) The reduction is from distinct-input 3-partition which is strongly NP-hard, i.e., intractable also if the input is given in unary, as is the case here. Given as input a set $S$ of $3m$ positive integers having sum $mT$, we must determine if we can partition $S$ into triples that all have sum $T$. The numbers are assumed to be strictly between $T/4$ and $T/2$: this ensures that the sum of strictly less than 3 numbers is always $<T$ and the sum of strictly more than 3 numbers is always $>T$.
The input strings are then the following (all distinct):
- $3m$ strings $a^i$ for each $i \in S$
- $m$ strings $b^i$ for $1 \leq i \leq m$
The target string is: $\bigodot_{1 \leq i \leq m} a^T b^i$.
If there is a solution to the unary 3-partition instance then we obtain a solution to the problem by concatenating the strings to form the triples of the solution, separated by the $m$ other strings in the correct order. Conversely, given a solution to the problem, we know that the $m$ blocks $b^i$ can only be achieved by the $m$ strings of the second kind, the only way to achieve $m$ blocks is to use them in the order $b^1, \ldots, b^m$. We can partition the strings of the first kind based on where they occur between these factors. The fact that the integers are strictly between $T/4$ and $T/2$ ensures that we have 3 strings per class in the partition, and they sum to $T$, giving a solution to the 3-partition problem.