Indeed it is pretty long ^^
It looks like you use shortcuts when it's clear that certain patterns have repeated characters.
You are right.
Let’s say i have this string : str = "aaaabbbccdf"
First i will look at all the repeating letters.
There are 4 'a', 3 'b', 2 'c'.
If there are no repeating letters, the answer is simply str.length! = 11! = 39916800.
Now i take the first group of repeating letters, "aaaa", i will not take into consideration any of the other letters, and call them "x".
from it, i will build any of the strings which possibly have no repeating letters :
I call these string "form", because they account for a particular form of the strings, a pattern (really i am not good with words…).
I know that each of these forms, account for 120960 possibilities :
I took the 11! possibilities i had, and divided it by the numbers of possibilities to place the 4 'a' in the string, that is : (11)! / (C(11, 4)) = 120960
Now i don’t know what happen with the 'x', so i will have to take each of these forms, to see how much correct strings they contain, let imagine i want to calculate the number of correct strings in this form : "axaxaxaxxxx"
First i will replace the 'a' by '|', "|x|x|x|xxxx" (it will represent the fact that there are separations between the letters)
Now i will look at my second group of repeating letters, the 3 'b', and i will do the same thing than with the 'a':
I know that each of these forms account for 120960 / C(7, 3) = 3456 possibilities.
And here, if you look the last form "x|x|b|xbxb", you can see that this form can only contain good strings, you can replace the 'x' by whatever letters, you will still have no repeating letters (i call it a perfect form in my program).
So i know i will not have to go further, and i just skipped 3456 possibilities to test for.
I continue like it for each group of repeating letters.
At the end, i know that each "x" will be a different letters, so i don’t need to go further, and i just have to sum everything.
It is pretty fast because :
1) I basically skip all the wrong strings. (but that is just like what you can do by improving your program)
2) More importantly, i add the good strings by big chunk, using "form" which are accounting for a lot of them.
Now i am sure i can still improve it a lot, using symmetry or things like that.
What would be good would be a purely mathematical solution, but i took more time to search for one, that to actually found and program this solution, so i gave up on that.