Lexicographic rank of a string among all its substrings | C # program for the above approach ; Function to find lexicographic rank of String among all its subString ; Length of String ; Traverse the given String and store the indices of each character ; Extract the index ; Store it in the vector ; Traverse the alphaIndex array lesser than the index of first character of given String ; If alphaIndex [ i ] size exceeds 0 ; Traverse over the indices ; Add count of subString equal to n - alphaIndex [ i , j ] ; Store all subStrings in a vector str starting with the first character of the given String ; Insert the current character to subString ; Store the subString formed ; Sort the subString in the lexicographical order ; Find the rank of given String ; increase the rank until the given String is same ; If subString is same as the given String ; Add 1 to rank of the given String ; Driver Code ; Given String ; Function Call
using System ; using System . Collections . Generic ; class GFG { static int lexicographicRank ( char [ ] s ) { int n = s . Length ; List < int > [ ] alphaIndex = new List < int > [ 26 ] ; for ( int i = 0 ; i < alphaIndex . Length ; i ++ ) alphaIndex [ i ] = new List < int > ( ) ; for ( int i = 0 ; i < s . Length ; i ++ ) { int x = s [ i ] - ' a ' ; alphaIndex [ x ] . Add ( i ) ; } int rank = 0 ; for ( int i = 0 ; i < 26 && ' a ' + i < s [ 0 ] ; i ++ ) { if ( alphaIndex [ i ] . Count > 0 ) { for ( int j = 0 ; j < alphaIndex [ i ] . Count ; j ++ ) { rank = rank + ( n - alphaIndex [ i ] [ j ] ) ; } } } List < String > str = new List < String > ( ) ; for ( int i = 0 ; i < alphaIndex [ s [ 0 ] - ' a ' ] . Count ; i ++ ) { String subString = " " ; int j = alphaIndex [ s [ 0 ] - ' a ' ] [ i ] ; for ( ; j < n ; j ++ ) { subString += ( s [ j ] ) ; str . Add ( subString ) ; } } str . Sort ( ) ; for ( int i = 0 ; i < str . Count ; i ++ ) { if ( ! str [ i ] . Equals ( String . Join ( " " , s ) ) ) { rank ++ ; } else { break ; } } return rank + 1 ; } public static void Main ( String [ ] args ) { String str = " enren " ; Console . Write ( lexicographicRank ( str . ToCharArray ( ) ) ) ; } }