CareerCup

Just do it the way we manually do it :
Sort the string and swap elements of the string in lexicographic order, while doing this keep count of the number strings that come before the current string in lexicographic order.
Also take care of duplicates while counting and swapping.
Eg:
For string 'dbace' :
1. sort : abcde
2. count permutation starting with a : 24
3. count permutation starting with b : 24
4. count permutation starting with c : 24
5. count permutation starting with 2nd letter as a : 6

int findCount(string str, int start, int end)
{
   int length = end-start+1;
   int count = factorial(length);
   int i=start;
   while(i< end)
   {
     int rep=1; 
     bool flag = true; 
     while(str[i] == str[i+1]) //counting number of repitions
     {
        flag = false;
        rep++;        
        i++;
     }
     if(flag)
      i++;
     count = count/ factorial(rep); //dividing by repitions!
   }
   return count;
}
int permRank(string str)
{
     if(str == "")
      return 0;
     int count =0;
     string sorted(str);
     sort(sorted.begin(),sorted.end());
     
     for(int i=0;i<sorted.length()-1;i++)
     {
        int rem;
        int j=i+1;
        
        while(sorted[i] != str[i])
        {
          rem = findCount(sorted,i+1,sorted.length()-1);
          count += rem;
          cout<<sorted<<"--->"<<rem<<endl;
          while(sorted[i] == sorted[j]) // don't swap if there is a duplicate
             j++; 
          swap(sorted,i,j);
          j++;          
        }
     }
     return count;
}

what if charcters are not necessarily unique?

K=n-1//n is the string length
For(i=0 to n)
{
      For(j=i+1 to n )
      {
           If(a[i]>a[j])
               S+= k!
       }
}return s+1

This can be broken into sub-problems. Here is the recurrence relation

LexicographicRank(A) =  1  (when A has just 1 char or if A is empty)
                  otherwise
LexicographicRank(A) =  Rank(A.charAt(0), A) * LexicographicRank(A.substring(1))
Rank(char c, String A)  = #(unique characters in A < c) + 1
e.g rank of C in "CDA" is 2

1) Sort the permuation using LSD or MSD sort with O(n)
2) put the rank and permutation into hash table
3)Search

int ranking(String s1){
	String sorted =sort(s1);
        int rank =0,temp=0,len =sorted.length();
        for(int i=0;i<len;i++){
            int start =0;
            int flag =0;
            int remLen =sorted.length()-start-1;
            while(start<sorted.length()){
                if(s1.charAt(i)!=sorted.charAt(start)){
                    rank = rank + factorial(remLen);
                }
                if(flag==0){
                    String c =sorted.charAt(start)+"";
                    sorted =sorted.replaceFirst(c,"");
                    len =sorted.length();flag=1;
                    break;
                }
                start++;
            }
        }
        return (rank+1);
}

#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;
}
}

{{
#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;
}
}
}}