In this article, we will discuss the lexicographic rank of a string in C++. But before going to its implementation, we must know about the Lexicographic.
Lexicographic or lexicographical ordering (commonly referred to as alphabetical or dictionary arranging) is the organization of words according to the alphabetical order of each component letter.
Problem statement:
Find the rank of a string str among all its modifications when sorted lexicographically.
Example:
Input: string = "cab"
Output: 5
Explanation: If all the given string's permutations are organized lexicographically, they will look like "abc", "acb", "bac", "bca", "cab" , and "cba" . It is clear from this that the rank of the string is 5.
The naive approach is to produce all the permutations in lexicographic sequence and save the rank of the current string. Check if the created permutation matches the input string and return the rank of the string.
Algorithm
Create a recursive function to calculate the factorial of a given number.
fact(num):
if num <= 1:
return 1 return num * fact(num- 1)
Create a function that computes the rank of a string in lexicographic permutation order.
find_Rank(st):
Determine the length of the provided string.
Set the rank to 1 at the start.
Loop through the string's characters one by one.
Create a variable to count the number of characters smaller than st[i].
After st[i], loop over the characters.
Update the rank based on the number of characters less than st[I].
Return the rank of the input string.
Filename: StringOrder.cpp
#include <bits/stdc++.h>
using namespace std;
// Create a recursive function to calculate the factorial for a given number.
int fact(int num) {
//Initializing the base condition
if(num <= 1) {
return 1;
}
// Recursive case: return the number of times the factorial with a value of num-1.
return num * fact(num - 1);
}
// Create a function that computes the rank of a string in lexicographic permutation order.
int findRanks(string str) {
//Determine the length of the input string
int num = str.length();
// initialising the rank as 1
int ranks = 1;
// Every single character in the string is looped through.
for(int i = 0; i < num; i++) {
// Create a variable to count the number of characters smaller than str[i].
int c = 0;
// After str[I], loop over each character.
for(int j = i + 1; j < num; j++) {
// If str[i] is higher than str[j], the count variable is increased.
if(str[i] > str[j]) {
c++;
}
}
//The rank should be updated depending on the number of characters less than str[I]
// multiplied by the factorial corresponding to the number of available characters.
ranks += c * fact(num - i - 1);
}
// The highest possible rank of the supplied string is returned.
return ranks;
}
// Mail section
int main() {
// defining the given input string
string strs = "student";
// Use the findRank function to find the position at the top of the test text and print the result.
cout << findRanks(strs) << endl;
//return 0 indicates that the program was completed.
return 0;
}
Output:
Using the permutation concept, compute the lexicographic rank of a String:
The problem can be solved using the concept of permutation, which is based on the following idea:
Determine how many lexicographically smaller strings may be created when all characters up to that index are fixed. It will return the strings that are smaller than that, and we will be able to determine the rank.
To put the concept into practice, take the following actions:
- Iterate through the string from i = 0 to the length of the string:
- Determine the number of characters that are less than the current character.
- Calculate the number of lexicographically smaller strings.
- Add that value to the rank.
- Finally, multiply 1 by rank and return the result as the required answer.
Filename: StringOrder2.cpp
+=// C++ Program for finding the lexicographic order of the string
#include <bits/stdc++.h>
using namespace std;
//A utility function for calculating the factorial of the number
int facts(int num) {
return (num <= 1) ? 1 : num * facts(num - 1);
}
// A utility function for counting the smaller characters to the right of the array[low].
int findtheSmallerInRight(string strs, int l, int h)
{
int countRights = 0, i;
for (i = l+ 1; i <= h; ++i)
if (strs[i] < strs[l])
++countRights;
return countRights;
}
// A function for determining the rank of a string in all character combinations.
int findtheRanks(string str)
{
int length = str.size();
int muls = facts(length);
int ranks= 1;
int countRights;
int i;
for (i = 0; i < length; ++i) {
muls /= length - i;
////Count the number of characters less than str[i] // from str[i+1] to str[length-1]
countRights = findtheSmallerInRight(str, i, length - 1);
ranks countRights * muls;
}
return ranks;
}
// Driver code
int main()
{
string strs= "student";
// Function calling
cout << findtheRanks(strs);
return 0;
}
Output:
A String's lexicographic rank in linear time:
The solution follows the same logic as the preceding technique. The time complexity can be decreased by establishing an auxiliary array of size 256 . Let's create an array that stores the total number of characters in the string that are less than the ith character and update it following each index of the given string during string iterations.
Filename: StringRank.cpp
//Program for finding the rank of a string using Linear Time complexity
#include <bits/stdc++.h>
using namespace std;
#define MAX_CHAR 256
// a function for finding the factorial of a number
int fact(int num) {
return (num <= 1) ? 1 : num * fact(num- 1);
}
// Create a count array with a value at each index.
// includes the number of smaller characters in the entire string
void populateAndIncreasingCount(int* c, string st)
{
int i;
for (i = 0; st[i]; ++i)
++c[st[i]];
for (i = 1; i < MAX_CHAR; ++i)
c[i] += c[i - 1];
}
///Removes a character ch from the count[] array, which was created by populateAndIncreasingCount().
void updatecount(int* c, char ch)
{
int i;
for (i = ch; i < MAX_CHAR; ++i)
--c[i];
}
//A function for determining the rank of a string in all permutations of individual characters.
int findRanks(string st)
{
int length = st.size();
int muls = fact(length);
int ranks = 1, i;
//initialising with 0
int c[MAX_CHAR] = { 0 };
// Fill up the count array so that c[I]
// includes the count of characters in st
//that have a value less than i.
populateAndIncreasingCount(c,st);
for (i = 0; i < length; ++i) {
muls /= length - i;
ranks += c[st[i] - 1] * muls;
//reducing the count
updatecount(c, st[i]);
}
return ranks;
}
int main()
{
string st = "student";
// function calling
cout << "The rank of the string is "<<findRanks(st);
return 0;
}
Output:
The rank of the string is 2617
Complexity:
Time Complexity: O(N)
Space Complexity: O(1)