Table of Contents

## Find the lexicographic rank of a string. (string without duplicates)

### Example

**Input string :** “CAB”

**Output :** Rank is 5

**Total possible permutations are :** ABC, ACB, BAC, BCA, CAB, CBA(lexicographic order)

Therefore, rank is 5

**Time complexity : O(n)**

## Algorithm

**a.** Initialize rank = 1.

**b.** Traverse in the string, for every char find the characters less than it.

**c.** Add all possible permutations with smaller characters to the rank and return the final rank.

Do this by,

**1.** Create an auxiliary count array, and store the count of smaller characters in the whole string.

**2.** For every character count number of characters smaller than string[i] from string[i+1] to string[len-1]

**3.** After adding it to rank.

**4.** Reduce count of characters greater than string[i], by removing the current character.

**d.** Return the final rank.

### Algorithm working

**Input string :** “codes”

Apply algorithm,

Initialize rank = 1,

**a)** i = 0, character = ‘c’

letters less than c in the right are NULL,

Move forward.

**b)** i = 1, character = ‘o’

letters less than o in the right are d, e

c d _ _ _ → 3!

c e _ _ _ → 3!

rank = rank + 3! + 3!

rank = 13

**c)** i = 2, character = ‘d’

letters less than d in the right are NULL

Move forward.

**d)** i = 3, character = ‘e’

letters less than e in the right are NULL

Move forward.

**e)** i = 4, character = ‘s’

letters less than d in the right are NULL

End here,

Final rank = 13.

Therefore, rank of “codes” = 13

## C++ Program

#include <bits/stdc++.h> using namespace std; #define ASCII_VALUES 256 //recursive function to find factorial function int fact(int n) { if (n<=1) { return 1; } else { return n * fact(n-1); } } //function to store the count of chatcters which are smaller i n the whole string //stores in count array void CreateCountArray(int* count, char* string) { int i; for(i = 0; string[i]; ++i ) { ++count[ string[i] ]; } for( i = 1; i < 256; ++i ) count[i] += count[i-1]; } //count array by removing the character ch void UpdateCountArray(int* count, char ch) { for(int i = ch; i < ASCII_VALUES; ++i ) { count[i] = count[i] - 1; } } int LexicographicRank(char* string) { int len = strlen(string); int per = fact(len); //Initialize rank = 1 and countarray with zeroes int rank = 1; int count[ASCII_VALUES] = {0}; //createcount array CreateCountArray(count, string); for (int i = 0; i < len; ++i) { per = per/(len - i); rank = rank + (count[ string[i] - 1] * per); //update count array by removing the current character UpdateCountArray (count, string[i]); } //return final rank return rank; } //Main function int main() { char string[] = "codes"; cout<<LexicographicRank(string); return 0; }

Try It