Lexicographic rank of a Binary String
Given a binary string S of length N, the task is to find the lexicographic rank of the given string.
Examples:
Input: S = “001”
Output: 8
Explanation:
Strings in order of their increasing rank:
“0” = 1,
“1” = 2,
“00” = 3,
“01” = 4,
“10” = 5,
“11” = 6,
“000” = 7,
“001” = 8.Input: S = “01”
Output: 4
Naive Approach: The simplest approach is to generate all possible binary strings (consisting of 0s and 1s) up to length N and store them in an array. Once done, sort the array of strings in lexicographic order and print the index of the given string in the array.
Time Complexity: O(2N)
Auxiliary Space: O(1)
Efficient Approach: The idea is to generate a binary string consisting of 0s and 1s by replacing every occurrence of ‘a’ with 0 and ‘b’ with 1. Therefore, the strings in the list become:
“a” = 0,
“b” = 1,
“aa” = 00,
“ab” = 01,
“ba” = 10,
“bb” = 11,
“aaa” = 000,
“aab” = 001 and so on.
It can be observed that for a string of size N, there exist (2N – 2) strings of length less than N before that given string. Let it be equal to X. Now, its lexicographic position among strings of length N can be calculated by converting the string into its decimal equivalent number and adding 1 to it. Let it be equal to Y.
Rank of a string = X + Y + 1
= (2N – 2) + Y + 1
= 2N + Y – 1
Below is the implementation of the above approach:
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
Time Complexity: O(N)
Auxiliary Space: O(N)