Given a sequence which contains only various amounts of the numbers 1, 2, 3, and 4 (examples: 13244, 4442, etc), I want to count all its permutations such that no two adjacent numbers are the same. I believe it is O(N! \* N) and want to know if there is a better one out there. Anyone have any ideas?

```
 class Ideone
    {
        static int permutationCount++;
        public static void main(String[] args) {
            String str = "442213";
            permutation("", str);
            System.out.println(permutationCount);
        }

        private static void permutation(String prefix, String str) {
            int n = str.length();
            if (n == 0){
                boolean bad = false;
                //Check whether there are repeating adjacent characters
                for(int i = 0; i < prefix.length()-1; i++){
                    if(prefix.charAt(i)==prefix.charAt(i+1))
                        bad = true;
                }
                if(!bad){
                    permutationCount++;
                }
            }
            else {
                //Recurse through permutations
                for (int i = 0; i < n; i++)
                    permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
            }
        }
    }

```