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)