string ranking algo

Given a string, find its rank among all its permutations sorted lexicographically. For example, rank of “abc” is 1, rank of “acb” is 2, and rank of “cba” is 6. 

------------------------------------------------------editorial-----------------------------------------------------------------------

if string dont have duplicate elements than 

For simplicity, let us assume that the string does not contain any duplicated characters.

One simple solution is to initialize rank as 1, generate all permutations in lexicographic order. After generating a permutation, check if the generated permutation is same as given string, if same, then return rank, if not, then increment the rank by 1. The time complexity of this solution will be exponential in worst case. Following is an efficient solution.

Let the given string be “STRING”. In the input string, ‘S’ is the first character. There are total 6 characters and 4 of them are smaller than ‘S’. So there can be 4 * 5! smaller strings where first character is smaller than ‘S’, like following

R X X X X X
I X X X X X
N X X X X X
G X X X X X

Now let us Fix S’ and find the smaller strings staring with ‘S’.

Repeat the same process for T, rank is 4*5! + 4*4! +…

Now fix T and repeat the same process for R, rank is 4*5! + 4*4! + 3*3! +…

Now fix R and repeat the same process for I, rank is 4*5! + 4*4! + 3*3! + 1*2! +…

Now fix I and repeat the same process for N, rank is 4*5! + 4*4! + 3*3! + 1*2! + 1*1! +…

Now fix N and repeat the same process for G, rank is 4*5! + 4*4 + 3*3! + 1*2! + 1*1! + 0*0!

Rank = 4*5! + 4*4! + 3*3! + 1*2! + 1*1! + 0*0! = 597

Since the value of rank starts from 1, the final rank = 1 + 597 = 598

but in our main problem string can have duplicates also , so we have to take care of this case also ,,,

for that we need a method that can return number of strings possible if some  characters are repeated

//  this function can easily calculate this    

// here n  no of characters going to use 

// cnt[i] is frequency of ith character 

lli count(int n)

 {

    lli ret = 1;

    

    for (int i = 0; i < 26; i++) 

{

        ret *= ncr[n][cnt[i]];

        n -= cnt[i];

   

    }

    return ret;

}

now rest things are same 

---------------------------------------------code---------------------------------------------------------------------------

#include<bits/stdc++.h>

using namespace std;

typedef long long int lli;

int cnt[30];

lli ncr[20][20];

// this function will return number of valid string of n remaining characters

lli count(int n)

 {

    lli ret = 1;

    

    for (int i = 0; i < 26; i++) 

{

        ret *= ncr[n][cnt[i]];

        n -= cnt[i];

   

    }

    return ret;

}

int main()

 {

  for(int i=0;i<=20;i++)

   {

     ncr[i][0]=1;

     ncr[i][i]=1;

     for(int j=1;j<i;j++)

      {

       ncr[i][j]=ncr[i-1][j]+ncr[i-1][j-1];

}

  }

  

  

  

  int t;

   cin>>t;

   while(t--)

    {

      string s;

        cin>>s;

        int len=s.length();

        for(int i=0;i<len;i++)

         {

          cnt[s[i]-'a']++;

}

lli ans=0;

 for(int i=1;i<=len;i++)

  {

  

  // cout<<i<<endl;

   for(int j=0;j<=25;j++)

    {

      if(s[i-1]>(j+'a') && cnt[j])

       {

       

          cnt[j]--;

         ans+=count(len-i);

         cnt[j]++;

 }

   }

   

   cnt[s[i-1]-'a']--;

     

  }

  cout<<ans+1<<endl;

}

 }