Lexicographic rank of a string | A O ( n ) solution for finding rank of string ; all elements of count [ ] are initialized with 0 ; A utility function to find factorial of n ; Construct a count array where value at every index contains count of smaller characters in whole string ; Removes a character ch from count [ ] array constructed by populateAndIncreaseCount ( ) ; A function to find rank of a string in all permutations of characters ; Populate the count array such that count [ i ] contains count of characters which are present in str and are smaller than i ; count number of chars smaller than str [ i ] fron str [ i + 1 ] to str [ len - 1 ] ; Reduce count of characters greater than str [ i ] ; Driver code
MAX_CHAR = 256 ; NEW_LINE count = [ 0 ] * ( MAX_CHAR + 1 ) ; NEW_LINE def fact ( n ) : NEW_LINE INDENT return 1 if ( n <= 1 ) else ( n * fact ( n - 1 ) ) ; NEW_LINE DEDENT def populateAndIncreaseCount ( str ) : NEW_LINE INDENT for i in range ( len ( str ) ) : NEW_LINE INDENT count [ ord ( str [ i ] ) ] += 1 ; NEW_LINE DEDENT for i in range ( 1 , MAX_CHAR ) : NEW_LINE INDENT count [ i ] += count [ i - 1 ] ; NEW_LINE DEDENT DEDENT def updatecount ( ch ) : NEW_LINE INDENT for i in range ( ord ( ch ) , MAX_CHAR ) : NEW_LINE INDENT count [ i ] -= 1 ; NEW_LINE DEDENT DEDENT def findRank ( str ) : NEW_LINE INDENT len1 = len ( str ) ; NEW_LINE mul = fact ( len1 ) ; NEW_LINE rank = 1 ; NEW_LINE populateAndIncreaseCount ( str ) ; NEW_LINE for i in range ( len1 ) : NEW_LINE INDENT mul = mul // ( len1 - i ) ; NEW_LINE rank += count [ ord ( str [ i ] ) - 1 ] * mul ; NEW_LINE updatecount ( str [ i ] ) ; NEW_LINE DEDENT return rank ; NEW_LINE DEDENT str = " string " ; NEW_LINE print ( findRank ( str ) ) ; NEW_LINE