Lexicographic rank of a string among all its substrings | Java 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
import java . util . * ; class GFG { static int lexicographicRank ( char [ ] s ) { int n = s . length ; Vector < Integer > [ ] alphaIndex = new Vector [ 26 ] ; for ( int i = 0 ; i < alphaIndex . length ; i ++ ) alphaIndex [ i ] = new Vector < Integer > ( ) ; 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 ] . size ( ) > 0 ) { for ( int j = 0 ; j < alphaIndex [ i ] . size ( ) ; j ++ ) { rank = rank + ( n - alphaIndex [ i ] . get ( j ) ) ; } } } Vector < String > str = new Vector < String > ( ) ; for ( int i = 0 ; i < alphaIndex [ s [ 0 ] - ' a ' ] . size ( ) ; i ++ ) { String subString = " " ; int j = alphaIndex [ s [ 0 ] - ' a ' ] . get ( i ) ; for ( ; j < n ; j ++ ) { subString += ( s [ j ] ) ; str . add ( subString ) ; } } Collections . sort ( str ) ; for ( int i = 0 ; i < str . size ( ) ; i ++ ) { if ( ! str . get ( i ) . equals ( String . valueOf ( s ) ) ) { rank ++ ; } else { break ; } } return rank + 1 ; } public static void main ( String [ ] args ) { String str = " enren " ; System . out . print ( lexicographicRank ( str . toCharArray ( ) ) ) ; } }