Permutations of a string
The number of permutations of n choose n items is always going to be n!. The way to optimize the solution is to prune the permutations to those that might solve the problem. This requires domain knowledge.

For example if the problem involves ordinary English words all permutations  matching *qz* or *mA* can be eliminated.

Incidentally, \$O(n*n!)\$ can be shortened to \$O(n!)\$ since it is roughly \$O((n+1)!)\$