CountNoRepPerms.java

public class CountNoRepPerms {
   public static long recur(int[] hist2, int prev, int uniqueChars) {
      if (hist2[0] == uniqueChars) return 1;
      int out = 0;
      for (int i = 1; i < hist2.length; i++) {
         int count = i == prev ? hist2[i]-1 : hist2[i];
         if (count > 0) {
            hist2[i]--;
            hist2[i-1]++;
            out += count*recur(hist2, i-1, uniqueChars);
            hist2[i-1]--;
            hist2[i]++;
         }
      }
      return out;
   }

   public static long countNoRepPerms(String input) {
      int[] hist = new int[Character.MAX_VALUE+1];
      int uniqueChars = 0, maxChar = 0;

      for (char c : input.toCharArray()) {
         hist[c]++;
         maxChar = Math.max(maxChar, hist[c]);
      }

      int[] hist2 = new int[maxChar+1];
      for (int i : hist) {
         if (i != 0) {
            hist2[i]++;
            uniqueChars++;
         }
      }
      return recur(hist2, -1, uniqueChars);
   }
}