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;

}

 }

EXCEL SHEET NAMING ALGO

MS Excel columns has a pattern like A, B, C, … ,Z, AA, AB, AC,…. ,AZ, BA, BB, … ZZ, AAA, AAB ….. etc. In other words, column 1 is named as “A”, column 2 as “B”, column 27 as “AA”.

Given a column number, find its corresponding Excel column name. Following are more examples.

Input          Output
 26             Z
 51             AY
 52             AZ
 80             CB
 676            YZ
 702            ZZ
 705            AAC

-----------------------------------EDITORIAL----------------------------------------------------------

THIS PROBLEM CAN BE SOLVED IN MANY MAYS , 

I SOLVED THIS IN 2 WAYS 

1ST APPROACH 

FIRST FIND LENGTH OF THE LONGEST STRING THAT  CAN BE THE ANSWER OF THE GIVEN NUMBER 

NOW DECREASE THE NUM BY ALL POSSIBLE STRING OF LEN-1,

NOW PROBLEM REDUCE TO ,  WE HAVE TO FIND NTH ( REMAINING N )   PERMUTATION OF THE STRING OF LENGTH LEN , ( WE HAVE AMPLE NUMBER OF EACH CHARACTER ) 

THIS PROBLEM CAN EASILY SOLVE BY 1 BY FIXING CHARACTERS  STARTING FROM 

THE MSB POSITION ( THIS PROBLEM  IS SIMILAR TO MY LAST POST  ONLY DIFFERENCE   IS THAT HERE WE HAVE  NO RESTRICTION ON THE NUMBER OF CHARACTERS )

-------------------------------------------CODE-------------------------------------------------------------

#include<bits/stdc++.h>

using namespace std;

typedef long long int lli;

  lli len=0;

  lli fact[11];

  lli solve(lli cur_pos,lli rem)

   {

    if(cur_pos>len)

     {

      cout<<endl;

      return 0;

}

else

{

lli i=0;

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

  {

   lli  cov=fact[len-cur_pos];

   if(cov>=rem) break;

   else

   rem-=cov;

   

  }

  printf("%c",(char)(i+'a'));

  solve(cur_pos+1,rem);

}

   }

int main()

 {

  lli t;

  cin>>t;

 

  fact[0]=1;

  for(lli i=1;i<=10;i++) fact[i]=fact[i-1]*26;

   

  while(t--)

   {

    lli n;

     cin>>n;

    len=0;

     lli sum=0;

     lli prev=1;

     for(lli i=0;i<10;i++)

      {

      sum+=prev*26;

      prev*=26;

      len++;

      if(sum>=n) break;

     

  }

  for(int i=1;i<=len-1;i++) n-=fact[i];

    //n-=fact[len-1];

    //cout<<" reduce n "<<n<<endl;

 solve(1,n);

  }

   

 }

2ND  EASY APPROACH  # OBSERVATION 

Suppose we have a number n, let’s say 28. so corresponding to it we need to print the column name. We need to take remainder with 26.

If remainder with 26 comes out to be 0 (meaning 26, 52 and so on) then we put ‘Z’ in the output string and new n becomes n/26 -1 because here we are considering 26 to be ‘Z’ while in actual it’s 25th with respect to ‘A’.

Similarly if the remainder comes out to be non zero. (like 1, 2, 3 and so on) then we need to just insert the char accordingly in the string and do n = n/26.

Finally we reverse the string and print.

Example:
n = 700

Remainder (n%26) is 24. So we put ‘X’ in output string and n becomes n/26 which is 26.

Remainder (26%26) is 0. So we put ‘Z’ in output string and n becomes n/26 -1 which is 0.

Following is C++ implementation of above approach.

• C++
• Python

#include<iostream> #include<cstring> #define MAX 50 using namespace std;   // Function to print Excel column name for a given column number void printString(int n) {     char str[MAX];  // To store result (Excel column name)     int i = 0;  // To store current index in str which is result       while (n>0)     {         // Find remainder         int rem = n%26;           // If remainder is 0, then a 'Z' must be there in output         if (rem==0)         {             str[i++] = 'Z';             n = (n/26)-1;         }         else // If remainder is non-zero         {             str[i++] = (rem-1) + 'A';             n = n/26;         }     }     str[i] = '\0';       // Reverse the string and print result     cout << strrev(str) << endl;       return; }   // Driver program to test above function int main() {     printString(26);     printString(51);     printString(52);     printString(80);     printString(676);     printString(702);     printString(705);     return 0; }