Dada una string s que puede tener caracteres duplicados. Descubra el rango lexicográfico de s. s puede consistir en letras mayúsculas y minúsculas. Consideramos el orden lexicográfico de los caracteres como su orden de valor ASCII. De ahí que el orden lexicográfico de los caracteres sea ‘A’, ‘B’, ‘C’,…, ‘Y’, ‘Z’, ‘a’, ‘b’, ‘c’,…, ‘y’, ‘z ‘.
Ejemplos:
Entrada: “abab”
Salida: 2
Explicación: El orden lexicográfico es: “aabb”, “abab”, “abba”, “baab”, “baba”, “bbaa”. Por lo tanto, el rango de «abab» es 2.
Entrada: «settle»
Salida: 107
Requisito previo: rango lexicográfico de una string
Método:
El método aquí es un poco diferente de la versión sin repetición. Aquí también tenemos que ocuparnos de los caracteres duplicados. Veamos la string «settLe». Tiene repetición (2 ‘e’ y 2 ‘t’), así como letras mayúsculas (‘L’). ¡6 caracteres en total y el número total de permutaciones es 6!/(2!*2!).
Ahora hay 3 caracteres (2 ‘e’ y 1 ‘L’) en el lado derecho de ‘s’ que vienen antes de ‘s’ lexicográficamente. Si no hubiera repetición, ¡habría 3*5! strings más pequeñas que tienen el primer carácter menos que ‘s’. Pero a partir de la posición 0, hasta el final hay 2 ‘e’ y 2 ‘t’ (es decir, repeticiones). Por lo tanto, el número de posibles permutaciones más pequeñas con la primera letra más pequeña que ‘s’ es (3*5!)/(2!*2!).
De manera similar, si fijamos ‘s’ y miramos las letras desde el índice 1 hasta el final, entonces hay 1 carácter (‘L’) lexicográficamente menor que ‘e’. Y a partir de la posición 1 hay 2 caracteres repetidos (2 ‘e’ y 2 ‘t’). Por lo tanto, el número de posibles permutaciones más pequeñas con la primera letra ‘s’ y la segunda letra más pequeña que ‘e’ son (1*4!)/(2!*2!).
Del mismo modo, podemos formar la siguiente tabla:
flujo de trabajo:
1. Initialize t_count(total count) variable
to 1(as rank starts from 1).
2. Run a loop for every character of the string, string[i]:
(i) using a loop count less_than(number of smaller
characters on the right side of string[i]).
(ii) take one array d_count of size 52 and using a
loop count the frequency of characters starting
from string[i].
(iii) compute the product, d_fac(the product of
factorials of each element of d_count).
(iv) compute (less_than*fac(n-i-1))/(d_fac).
Add it to t_count.
3. return t_count
C++
// C++ program to find out lexicographic
// rank of a string which may have duplicate
// characters and upper case letters.
#include <iostream>
#include <vector>
using namespace std;
// Function to calculate factorial of a number.
long long fac(long long n)
{
if (n == 0 or n == 1)
return 1;
return n * fac(n - 1);
}
// Function to calculate rank of the string.
int lexRank(string s)
{
long long n = s.size();
// Initialize total count to 1.
long long t_count = 1;
// loop to calculate number of smaller strings.
for (int i = 0; i < n; i++)
{
// Count smaller characters than s[i].
int less_than = 0;
for (int j = i + 1; j < n; j++)
{
if (int(s[i]) > int(s[j]))
{
less_than += 1;
}
}
// Count frequency of duplicate characters.
vector<int> d_count(52, 0);
for (int j = i; j < n; j++)
{
// Check whether the character is upper
// or lower case and then increase the
// specific element of the array.
if ((int(s[j]) >= 'A') && int(s[j]) <= 'Z')
d_count[int(s[j]) - 'A'] += 1;
else
d_count[int(s[j]) - 'a' + 26] += 1;
}
// Compute the product of the factorials
// of frequency of characters.
long long d_fac = 1;
for (int ele : d_count)
d_fac *= fac(ele);
// add the number of smaller string
// possible from index i to total count.
t_count += (fac(n - i - 1) * less_than) / d_fac;
}
return (int)t_count;
}
// Driver Code
int main()
{
// Test case 1
string s1 = "abab";
cout << "Rank of " << s1 << " is: " << lexRank(s1)
<< endl;
// Test case 2
string s2 = "settLe";
cout << "Rank of " << s2 << " is: " << lexRank(s2)
<< endl;
return 0;
}
Java
// Java program to find out lexicographic
// rank of a String which may have duplicate
// characters and upper case letters.
class GFG {
// Function to calculate
// factorial of a number.
static long fac(long n)
{
if (n == 0 || n == 1)
return 1;
return n * fac(n - 1);
}
// Function to calculate
// rank of the String.
static int lexRank(String s)
{
long n = s.length();
// Initialize total count to 1.
long t_count = 1;
// loop to calculate
// number of smaller Strings.
for (int i = 0; i < n; i++)
{
// Count smaller
// characters than s[i].
long less_than = 0;
for (int j = i + 1; j < n; j++)
{
if (s.charAt(i)
> s.charAt(j))
{
less_than += 1;
}
}
// Count frequency of
// duplicate characters.
long[] d_count = new long[52];
for (int j = i; j < n; j++)
{
// Check whether the
// character is upper
// or lower case and
// then increase the
// specific element of
// the array.
if ((s.charAt(j) >= 'A')
&& s.charAt(j) <= 'Z')
d_count[s.charAt(j) - 'A'] += 1;
else
d_count[s.charAt(j) - 'a' + 26] += 1;
}
// Compute the product of the factorials
// of frequency of characters.
long d_fac = 1;
for (long ele : d_count)
d_fac *= fac(ele);
// add the number of smaller String
// possible from index i to total count.
t_count += (fac(n - i - 1)
* less_than) / d_fac;
}
return (int)t_count;
}
// Driver Code
public static void main(String[] args)
{
// Test case 1
String s1 = "abab";
System.out.print("Rank of " + s1
+ " is: " + lexRank(s1) + "\n");
// Test case 2
String s2 = "settLe";
System.out.print("Rank of " + s2
+ " is: " + lexRank(s2) + "\n");
}
}
// This code is contributed by gauravrajput1
C#
// C# program to find out
// lexicographic rank of a
// String which may have
// duplicate characters and
// upper case letters.
using System;
class GFG {
// Function to calculate
// factorial of a number.
static long fac(long n)
{
if (n == 0 || n == 1)
return 1;
return n * fac(n - 1);
}
// Function to calculate
// rank of the String.
static long lexRank(String s)
{
long n = s.Length;
// Initialize total
// count to 1.
long t_count = 1;
// loop to calculate number
// of smaller Strings.
for (long i = 0; i < n; i++)
{
// Count smaller characters
// than s[i].
long less_than = 0;
for (long j = i + 1; j < n; j++)
{
if (s[i] > s[j])
{
less_than += 1;
}
}
// Count frequency of
// duplicate characters.
long[] d_count = new long[52];
for (int j = i; j < n; j++)
{
// Check whether the character
// is upper or lower case and
// then increase the specific
// element of the array.
if ((s[j] >= 'A') && s[j] <= 'Z')
d_count[s[j] - 'A'] += 1;
else
d_count[s[j] - 'a' + 26] += 1;
}
// Compute the product of the
// factorials of frequency of
// characters.
long d_fac = 1;
foreach(long ele in d_count)
d_fac *= fac(ele);
// add the number of smaller
// String possible from index
// i to total count.
t_count += (fac(n - i - 1)
* less_than) / d_fac;
}
return t_count;
}
// Driver Code
public static void Main(String[] args)
{
// Test case 1
String s1 = "abab";
Console.Write("Rank of " + s1
+ " is: " + lexRank(s1) + "\n");
// Test case 2
String s2 = "settLe";
Console.Write("Rank of " + s2
+ " is: " + lexRank(s2) + "\n");
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program to find out lexicographic
// rank of a String which may have duplicate
// characters and upper case letters.
// Function to calculate
// factorial of a number.
function fac(n)
{
if (n == 0 || n == 1)
return 1;
return n * fac(n - 1);
}
// Function to calculate
// rank of the String.
function lexRank(s)
{
n = s.length;
// Initialize total count to 1.
let t_count = 1;
// loop to calculate
// number of smaller Strings.
for (let i = 0; i < n; i++)
{
// Count smaller
// characters than s[i].
let less_than = 0;
for (let j = i + 1; j < n; j++)
{
if (s[i]
> s[j])
{
less_than += 1;
}
}
// Count frequency of
// duplicate characters.
let d_count = new Array(52);
for(let i=0;i<52;i++)
d_count[i]=0;
for (let j = i; j < n; j++)
{
// Check whether the
// character is upper
// or lower case and
// then increase the
// specific element of
// the array.
if ((s[j] >= 'A')
&& s[j] <= 'Z')
d_count[s[j].charCodeAt(0) - 'A'.charCodeAt(0)] += 1;
else
d_count[s[j].charCodeAt(0) - 'a'.charCodeAt(0) + 26] += 1;
}
// Compute the product of the factorials
// of frequency of characters.
let d_fac = 1;
for (let ele=0;ele< d_count.length;ele++)
d_fac *= fac(d_count[ele]);
// add the number of smaller String
// possible from index i to total count.
t_count += (fac(n - i - 1)
* less_than) / d_fac;
}
return t_count;
}
// Driver Code
let s1 = "abab";
document.write("Rank of " + s1
+ " is: " + lexRank(s1) + "<br>");
// Test case 2
let s2 = "settLe";
document.write("Rank of " + s2
+ " is: " + lexRank(s2) + "<br>");
// This code is contributed by patel2127
</script>
Rank of abab is: 2 Rank of settLe is: 107
Complejidad temporal: O(n 2 )