I'm finding the number of permutations of the lexicographically smallest string.

For example, bbaa now the lexicographically smallest string is aabb So, the permutations are,

(1,2,3,4), (2,1,3,4), (1,2,4,3), (2,1,4,3) which is 4.

My idea for it (in python) was to find the smallest string (basically sort it into a string) and then, creating a counter which stores the count of each character.

Since, we don't need a string which becomes lexicographically larger, we can only swap the same characters.

Like, aaabbbcc so, a has 3 places, b has 3 places and c has only 2.

Which makes the number of permutations possible, (3*3*2)

And this can be implemented by multiplying the values of counter. But this approach is missing out on something important because, obviously, it doesn't pass. And I found a string, which deviates this approach:

hjkegfghjkdcoiuyg

Length: 18

Sorted: cdefggghhijjkkouy

Counter:

Counter({'g': 3, 'h': 2, 'j': 2, 'k': 2, 'c': 1, 'd': 1, 'e': 1, 'f': 1, 'i': 1, 'o': 1, 'u': 1, 'y': 1})

EDIT:

So according to my algorithm, the answer should be 24 as mentioned above. But the actual answer is '48' which is twice and I tried to figure out some relation or maybe a silly mistake, but there's no silly mistake.

CodePudding user response：

You need to multiply the factorials of the character counts. This is because 3 same letters creates 3! = 6 permutations: (1,2,3) (1,3,2) (2,1,3) (2,3,1) (3,1,2) (3,2,1)

With this example, 3! * 2! * 2! * 2! = 6 * 2 * 2 * 2 = 48.

CodePudding user response：

Counting permutations is done with factorials. Your answer should be 3! * 2! * 2! * 2!