Given a String count the possible Permutations that satisfy a condition. How to Optimize from O(N*N!)

Hi I recently came across an interesting question and had a hard time trying to optimize it beyond O(N*N!). Here is the question: Given a string, return the number of possible combination that satisfy the criteria:

1. The String must start with consonant (Anything not in 'aeiou')
2. String cannot have 2consecutive consonant or vowel.
3. For example, 'BAR' should return 2 for {'BAR,'RAB'} and 'AAB' should return 0 for {}

My Approach: I tried the most obvious way by writing a helper function that validates if a given string satisfy the above condition, then I generate all the permutation of the string and increase the count for each valid string generated. This approach has the complexity of O(N*N!) for the string permutation and possibly too slow for longer strings.

Then I tried to use naive counting approach to calculate by multiplying the choices for each position with the number of vowel and consonant, taking into account the constraints(Altering between Consonant and vowel). However this method is unable to handle duplicate character scenario such as: {BAB}

Can anyone provide insight on how to optimize this?

You have a solution that works for all unique characters.

If there is a duplicate (triplicate...) character, how much did you overcount?

For a k-tuple character, there are k! ways to order k unique characters and your result includes those but you should have only counted that as 1.

So divide your initial number by k! for each k-times repeated character in the input.