Dada una string binaria S de longitud N , la tarea es encontrar el rango lexicográfico de la string dada .
Ejemplos:
Entrada: S = “001”
Salida: 8
Explicación:
Strings en orden creciente:
“0” = 1,
“1” = 2,
“00” = 3,
“01” = 4,
“10” = 5,
“11” = 6,
“000” = 7,
“001” = 8.Entrada: S = “01”
Salida: 4
Enfoque ingenuo: el enfoque más simple es generar todas las strings binarias posibles ( que consisten en 0 y 1 ) hasta la longitud N y almacenarlas en una array. Una vez hecho esto, ordene la array de strings en orden lexicográfico e imprima el índice de la string dada en la array.
Complejidad temporal: O(2 N )
Espacio auxiliar: O(1)
Enfoque eficiente: la idea es generar una string binaria que consta de 0 y 1 reemplazando cada aparición de ‘a’ con 0 y ‘b’ con 1 . Por lo tanto, las strings en la lista se convierten en:
“a” = 0,
“b” = 1,
“aa” = 00,
“ab” = 01,
“ba” = 10,
“bb” = 11,
“aaa” = 000,
“aab” = 001 y así sucesivamente .
Se puede observar que para una string de tamaño N , existen (2 N – 2) strings de longitud menor que N antes de esa string dada. Sea igual a X. Ahora, su posición lexicográfica entre las strings de longitud N se puede calcular convirtiendo la string en su número decimal equivalente y sumando 1. Sea igual a Y.
Rango de una string = X + Y + 1
= (2 N – 2) + Y + 1
= 2 N + Y – 1
A continuación se muestra la implementación del enfoque anterior:
C++
//C++ program for the above approach
#include <iostream>
using namespace std;
// Function to find the rank of a string
void findRank(string s)
{
// Store the length of the string
int N = s.size();
// Stores its equivalent decimal value
string bin;
// Traverse the string
for (int i = 0; i < N; i++)
{
if (s[i] == '0')
bin += "0";
else
bin += "1";
}
// Store the number of strings of
// length less than N occurring
// before the given string
long long X = 1ll<<N;
// Store the decimal equivalent
// number of string bin
long long res = 0, val = 1;
for(int i = N - 1; i >= 0; i--)
{
if (bin[i] == '1')
res += (val);
val *= 2ll;
}
long long Y = res;
// Store the rank in answer
long ans = X + Y - 1;
// Print the answer
cout << ans;
}
// Driver program
int main()
{
string S = "001";
findRank(S);
return 0;
}
// This code is contributed by jyoti369.
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
public class Main {
// Function to find the rank of a string
static void findRank(String s)
{
// Store the length of the string
int N = s.length();
// Stores its equivalent decimal value
StringBuilder sb = new StringBuilder("");
// Traverse the string
for (int i = 0; i < N; i++) {
if (s.charAt(i) == '0')
sb.append('0');
else
sb.append('1');
}
String bin = sb.toString();
// Store the number of strings of
// length less than N occurring
// before the given string
long X = (long)Math.pow(2, N);
// Store the decimal equivalent
// number of string bin
long Y = Long.parseLong(bin, 2);
// Store the rank in answer
long ans = X + Y - 1;
// Print the answer
System.out.println(ans);
}
// Driver Code
public static void main(String[] args)
{
String S = "001";
findRank(S);
}
}
Python3
# Python program for the above approach
# Function to find the rank of a string
def findRank(s):
# Store the length of the string
N = len(s);
# Stores its equivalent decimal value
sb = "";
# Traverse the string
for i in range(0,N):
if (s[i] == '0'):
sb += str('0');
else:
sb += str('1');
bin = str(sb);
# Store the number of strings of
# length less than N occurring
# before the given string
X = pow(2, N);
# Store the decimal equivalent
# number of string bin
Y = int(bin);
# Store the rank in answer
ans = X + Y - 1;
# Print the answer
print(ans);
# Driver Code
if __name__ == '__main__':
S = "001";
findRank(S);
# This code is contributed by shikhasingrajput
C#
// C# program to implement
// the above approach
using System;
class GFG
{
// Function to find the rank of a String
static void findRank(string s)
{
// Store the length of the String
int N = s.Length;
// Stores its equivalent decimal value
string bin = "";
// Traverse the String
for (int i = 0; i < N; i++)
{
if (s[i] == '0')
bin += "0";
else
bin += "1";
}
// Store the number of string s of
// length less than N occurring
// before the given String
int X = 1<<N;
// Store the decimal equivalent
// number of String bin
int res = 0, val = 1;
for(int i = N - 1; i >= 0; i--)
{
if (bin[i] == '1')
res += (val);
val *= 2;
}
int Y = res;
// Store the rank in answer
int ans = X + Y - 1;
// Print the answer
Console.Write(ans);
}
// Driver Code
public static void Main()
{
string S = "001";
findRank(S);
}
}
// This code is contributed by splevel62.
Javascript
<script>
// Javascript program for the above approach
// Function to find the rank of a string
function findRank( s)
{
// Store the length of the string
var N = s.length;
// Stores its equivalent decimal value
var bin = "";
// Traverse the string
for (var i = 0; i < N; i++)
{
if (s[i] == '0')
bin += "0";
else
bin += "1";
}
// Store the number of strings of
// length less than N occurring
// before the given string
var X = 1<<N;
// Store the decimal equivalent
// number of string bin
var res = 0, val = 1;
for(var i = N - 1; i >= 0; i--)
{
if (bin[i] == '1')
res += (val);
val *= 2;
}
var Y = res;
// Store the rank in answer
var ans = X + Y - 1;
// Print the answer
document.write( ans);
}
// Driver program
var S = "001";
findRank(S);
</script>
8
Complejidad temporal: O(N)
Espacio auxiliar: O(N)