Number of distinct permutation a String can have | C ++ program to find number of distinct permutations of a string . ; Utility function to find factorial of n . ; Returns count of distinct permutations of str . ; finding frequency of all the lower case alphabet and storing them in array of integer ; finding factorial of number of appearances and multiplying them since they are repeating alphabets ; finding factorial of size of string and dividing it by factorial found after multiplying ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int MAX_CHAR = 26 ; int factorial ( int n ) { int fact = 1 ; for ( int i = 2 ; i <= n ; i ++ ) fact = fact * i ; return fact ; } int countDistinctPermutations ( string str ) { int length = str . length ( ) ; int freq [ MAX_CHAR ] ; memset ( freq , 0 , sizeof ( freq ) ) ; for ( int i = 0 ; i < length ; i ++ ) if ( str [ i ] >= ' a ' ) freq [ str [ i ] - ' a ' ] ++ ; int fact = 1 ; for ( int i = 0 ; i < MAX_CHAR ; i ++ ) fact = fact * factorial ( freq [ i ] ) ; return factorial ( length ) / fact ; } int main ( ) { string str = " fvvfhvgv " ; printf ( " % d " , countDistinctPermutations ( str ) ) ; return 0 ; }