Lexicographic Rank of a String - Arrays

Problem Statement: You are given a string, find its lexicographical rank among all its permutations.

Example:

Example 1:
Input: S = “abc”
Output: rank = 1 

Example 2:
Input: S = “cba”
Output: rank = 6

Solution:

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

First of all,

What is lexicographic order, lexicographical order is a generalization of the alphabetical order of the dictionaries to sequences of ordered symbols or, more generally, of elements of a totally ordered set.

In simple words, the rank of a word in a dictionary.

So how to approach the problem?

Solution 1:

Approach:

We will generate all the permutations in lexicographic order, and then check for the given string in the order, and then find the rank. If we find the match then we will output the rank, else we will just increment the ans by 1 to find the correct rank.

So for that,

Sort the string in increasing order.
Start generating the next higher permutation until all permutations are complete.

Code:

C++ Code

#include <bits/stdc++.h>

using namespace std;
int compare(const void * a,
  const void * b) {
  return ( * (char * ) a - * (char * ) b);
}
//finds the smallest character which is greater than first in str[l...h] 
int findCeil(char str[], char first, int l, int h) {
  int ceilIndex = l;
  for (int i = l + 1; i <= h; i++)
    if (str[i] > first && str[i] < str[ceilIndex])
      ceilIndex = i;
  return ceilIndex;
}
void sortedPermutations(char str[], vector < string > & v) {
  int size = strlen(str);
  qsort(str, size, sizeof(str[0]), compare); //sorting in increasing order 
  //printing permutations one by one 
  bool isFinished = false;
  while (!isFinished) {
    //cout << str << endl; 
    v.push_back(str);
    //find the next smaller rightmost character 
    int i;
    for (i = size - 2; i >= 0; --i)
      if (str[i] < str[i + 1])
        break;
    //if no such character exists , means we printed the last permuation
    if (i == -1)
      isFinished = true;
    else {
      //find the ceiling of that character in right 
      int ceilIndex = findCeil(str, str[i], i + 1, size - 1);
      ///swap first and second characters 
      swap(str[i], str[ceilIndex]);
      ///agauin sort it 
      qsort(str + i + 1, size - i - 1, sizeof(str[0]), compare);
    }
  }
}
int main() {
  char str[] = "rank";
  vector < string > v;
  sortedPermutations(str, v);
  cout << "Lexicographic rank is: ";
  for (int i = 0; i < v.size(); i++) {
    if (v[i] == "rank") {
      cout << i + 1 << endl; //because the indexing starts from zero 
    }
  }
  return 0;
}

Output:

Lexicographic rank is: 20

But, the time complexity of this solution is exponential, i.e., O(n^2 * n!) in the worst case, and is surely not a good solution to implement.

Solution 2:

Approach:

This is a simple approach, we used to find the rank of a word in a dictionary. And the calculations are also the same.

Example:

If we take the word “rank” , 
Total number of letters in the string - 4 
For the first character , ‘r’ , there are 3 words smaller than ‘r’ , in the alphabetical order. So , for r - 3*3! 
Now , for a - every word is greater than ‘a’ , so it will be 0*0! 
For n , - 1*2! 
For k , - 0*0! 
Adding them all - 3*3! + 0 + 1*2! + 0 = 20

So, now implementation – For each character, we need to know the number of characters smaller than that on the right, and the number of characters left in the string to be processed. For every character, – (no. of character smaller than that) * (no.of character left in the string)!

Code:

C++ Code

#include <bits/stdc++.h>

#include <string.h>

using namespace std;
int fact(int n) {
  if (n <= 1) {
    return 1;
  }
  return n * fact(n - 1);
}
int SmallerCharInRight(char * str, int low, int high) {
  int count = 0;
  for (int i = low + 1; i <= high; ++i) {
    if (str[i] < str[low])
      count++;
  }
  return count;
}
int findRank(char * str) {
  int len = strlen(str);
  int multiply = fact(len);
  int rank = 1;
  int i;
  for (i = 0; i < len; ++i) {
    // count number of chars smaller than str[i] // from str[i+1] to str[len-1] 
    int count = SmallerCharInRight(str, i, len - 1);
    multiply = multiply / (len - i);
    rank += count * multiply;
  }
  return rank;
}
int main() {
  char str[] = "bca";
  cout << "Lexiographic rank is: " << findRank(str);
  return 0;
}

Output:

Lexiographic rank is: 4

Time Complexity – O(n^2)

Space Complexity – O(1)

Approach 3 – (optimised)

We can also have an O(n) solution by using some space.

Let’s see, how it works?

In this, we will take an auxiliary array or frequency array of 256 characters, and use that array to store the smaller elements on the right.

Code:

C++ Code

#include <bits/stdc++.h>

using namespace std;
int fact(int n) {
  if (n <= 1) {
    return 1;
  }
  return n * fact(n - 1);
}
void populatecount(int * count, char * str) {
  //store the characters smaller than this in the count array 
  for (int i = 0; i < strlen(str); i++)
    count[str[i]]++;
  for (int i = 1; i < 256; i++)
    count[i] += count[i - 1];
}
void updatecount(int * count, char ch) {
  //after using a charcater , we need to decrease its count , so that the smaller 
  //elements in the right can be calculated correctly. 
  for (int i = ch; i < 256; i++)
    count[i]--;
}
int findRank(char * str) {
  int len = strlen(str);
  int mul = fact(len);
  int rank = 1;
  int count[256] = {
    0
  }; //first initialised with 0 
  populatecount(count, str); //populating the count 
  for (int i = 0; i < len; i++) {
    mul /= len - i;
    rank += count[str[i] - 1] * mul; //getting the rank 
    updatecount(count, str[i]); //updating the count of str[i] in the count array
  }
  return rank;
}
int main() {
  char str[] = "cba";
  cout << "Lexiographic rank is: " << findRank(str);
  return 0;
}

Output: Lexiographic rank is: 6

Time complexity – O(n)

Space complexity – O(n)

Special thanks to Ishita Dhiman for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article. If you want to suggest any improvement/correction in this article please mail us at [email protected]