Horje
K-th Lexicographically smallest binary string with A 0s and B 1s

Given three positive integers A, B, and K, the task is to find the Kth lexicographically smallest binary string that contains exactly A number of 0s and B number of 1s.

Example:

Input: A = 2, B = 2, K = 4
Output: 1001
Explanation: The lexicographic order of the strings is 0011, 0101, 0110, 1001.

Input: A = 3, B = 3, K = 7
Output: 010110

 

Approach: The above problem can be solved by using Dynamic Programming. Follow the below steps to solve this problem:

  • Initialize a 2D array dp[][] such that dp[i][j] will denote the total number of binary strings with i number of 0s and j number of 1s.
  • All the dp table values are initially filled with zeroes except dp[0][0] = 1 which denotes an empty string.
  • Now, dp[i][j] can be calculated as the sum of the total number of strings ending with 0(using the dp state as dp[i – 1][j]) and the string ending with 1(using the dp state as dp[i][j – 1]). So, the current dp state is calculated as dp[i][j] = dp[i – 1][j] + dp[i][j – 1].
  • After filling this dp table, a recursive function can be used to calculate the Kth lexicographically smallest binary string.
  • So, define a function KthString having parameters A, B, K, and dp.
  • Now, in each call of this recursive function:
    • If the value of dp[A][B] is at least K then only ‘0’ can be present at this position in the Kth lexicographically smallest binary string and then recursively call function for the state (A – 1, B).
    • Else ‘1’ is present here and recursively call function for the state (A, B – 1).
  • Print the answer according to the above observation.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Recursive function to find the Kth
// smallest binary string
string KthString(int A, int B, long long K,
                 vector<vector<int> >& dp)
{
    // Base Case
    if (A == 0) {
 
        // Return string of all 1's
        // of length B
        return string(B, '1');
    }
    if (B == 0) {
 
        // Return string of all 0's
        // of length A
        return string(A, '0');
    }
 
    if (K <= dp[A - 1][B]) {
        return "0" + KthString(
                         A - 1, B, K, dp);
    }
 
    else {
        return "1"
               + KthString(
                     A, B - 1,
                     K - dp[A - 1][B], dp);
    }
}
 
// Function to find the Kth lexicographically
// smallest binary string with exactly
// A zeroes and B ones
int KthStringUtil(int A, int B, int K)
{
    // Stores the recurring states
    vector<vector<int> > dp(
        A + 1, vector<int>(B + 1));
 
    // Calculate the dp values iteratively
    dp[0][0] = 1;
    for (int i = 0; i <= A; ++i) {
        for (int j = 0; j <= B; ++j) {
 
            if (i > 0) {
 
                // The last character was '0'
                dp[i][j] += dp[i - 1][j];
            }
            if (j > 0) {
 
                // The last character was '1'
                dp[i][j] += dp[i][j - 1];
            }
        }
    }
 
    // Print the binary string obtained
    cout << KthString(A, B, K, dp);
 
    return 0;
}
 
// Driver Code
int main()
{
    int A = 3, B = 3, K = 7;
    KthStringUtil(A, B, K);
 
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
 
class GFG {
 
    // Recursive function to find the Kth
    // smallest binary string
    static String KthString(int A, int B, long K, int[][] dp)
    {
       
        // Base Case
        if (A == 0) {
 
            // Return string of all 1's
            // of length B
            String ans = "";
            for (int i = 0; i < B; i++) {
                ans += '1';
            }
            return ans;
        }
        if (B == 0) {
 
            // Return string of all 0's
            // of length A
            String ans = "";
            for (int i = 0; i < A; i++) {
                ans += '0';
            }
            return ans;
        }
 
        if (K <= dp[A - 1][B]) {
            return "0" + KthString(A - 1, B, K, dp);
        }
 
        else {
            return "1"
                + KthString(A, B - 1, K - dp[A - 1][B], dp);
        }
    }
 
    // Function to find the Kth lexicographically
    // smallest binary string with exactly
    // A zeroes and B ones
    static int KthStringUtil(int A, int B, int K)
    {
        // Stores the recurring states
        int[][] dp = new int[A + 1][B + 1];
 
        // Calculate the dp values iteratively
        dp[0][0] = 1;
        for (int i = 0; i <= A; ++i) {
            for (int j = 0; j <= B; ++j) {
 
                if (i > 0) {
 
                    // The last character was '0'
                    dp[i][j] += dp[i - 1][j];
                }
                if (j > 0) {
 
                    // The last character was '1'
                    dp[i][j] += dp[i][j - 1];
                }
            }
        }
 
        // Print the binary string obtained
        System.out.println(KthString(A, B, K, dp));
 
        return 0;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int A = 3, B = 3, K = 7;
        KthStringUtil(A, B, K);
    }
}
 
// This code is contributed by Dharanendra L V.

Python3

# Python Program to implement
# the above approach
 
# Recursive function to find the Kth
# smallest binary string
def KthString(A, B, K, dp):
   
    # Base Case
    if (A == 0):
 
        # Return string of all 1's
        # of length B
        str = ""
        for i in range(B):
            str += '1'
         
        return str
     
    if (B == 0):
 
        # Return string of all 0's
        # of length A
        str = ""
        for i in range(A):
            str += '0'
        return str
 
    if (K <= dp[A - 1][B]):
        return "0" + KthString( A - 1, B, K, dp)
 
    else:
        return "1" + KthString( A, B - 1, K - dp[A - 1][B], dp)
     
 
# Function to find the Kth lexicographically
# smallest binary string with exactly
# A zeroes and B ones
def KthStringUtil(A, B, K):
   
    # Stores the recurring states
    dp = [0] * (A + 1)
 
    for i in range(len(dp)):
        dp[i] = [0] * (B + 1)
     
 
    # Calculate the dp values iteratively
    dp[0][0] = 1
    for i in range(A + 1):
        for j in range(B + 1):
 
            if (i > 0):
 
                # The last character was '0'
                dp[i][j] += dp[i - 1][j]
             
            if (j > 0):
 
                # The last character was '1'
                dp[i][j] += dp[i][j - 1]
         
 
    # Print the binary string obtained
    print(KthString(A, B, K, dp))
 
# Driver Code
A = 3
B = 3
K = 7
KthStringUtil(A, B, K)
 
# This code is contributed by gfgking.

C#

// C# program for the above approach
using System;
class GFG {
 
    // Recursive function to find the Kth
    // smallest binary string
    static string KthString(int A, int B, long K,
                            int[, ] dp)
    {
 
        // Base Case
        if (A == 0) {
 
            // Return string of all 1's
            // of length B
            string ans = "";
            for (int i = 0; i < B; i++) {
                ans += '1';
            }
            return ans;
        }
        if (B == 0) {
 
            // Return string of all 0's
            // of length A
            string ans = "";
            for (int i = 0; i < A; i++) {
                ans += '0';
            }
            return ans;
        }
 
        if (K <= dp[A - 1, B]) {
            return "0" + KthString(A - 1, B, K, dp);
        }
 
        else {
            return "1"
                + KthString(A, B - 1, K - dp[A - 1, B], dp);
        }
    }
 
    // Function to find the Kth lexicographically
    // smallest binary string with exactly
    // A zeroes and B ones
    static int KthStringUtil(int A, int B, int K)
    {
        // Stores the recurring states
        int[, ] dp = new int[A + 1, B + 1];
 
        // Calculate the dp values iteratively
        dp[0, 0] = 1;
        for (int i = 0; i <= A; ++i) {
            for (int j = 0; j <= B; ++j) {
 
                if (i > 0) {
 
                    // The last character was '0'
                    dp[i, j] += dp[i - 1, j];
                }
                if (j > 0) {
 
                    // The last character was '1'
                    dp[i, j] += dp[i, j - 1];
                }
            }
        }
 
        // Print the binary string obtained
        Console.WriteLine(KthString(A, B, K, dp));
 
        return 0;
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
        int A = 3, B = 3, K = 7;
        KthStringUtil(A, B, K);
    }
}
 
// This code is contributed by ukasp.

Javascript

<script>
        // JavaScript Program to implement
        // the above approach
 
        // Recursive function to find the Kth
        // smallest binary string
        function KthString(A, B, K,
            dp) {
            // Base Case
            if (A == 0) {
 
                // Return string of all 1's
                // of length B
                let str = "";
                for (let i = 0; i < B; i++) {
                    str += '1';
                }
                return str;
            }
            if (B == 0) {
 
                // Return string of all 0's
                // of length A
                let str = "";
                for (let i = 0; i < A; i++) {
                    str += '0';
                }
                return str;
 
            }
 
            if (K <= dp[A - 1][B]) {
                return "0" + KthString(
                    A - 1, B, K, dp);
            }
 
            else {
                return "1"
                    + KthString(
                        A, B - 1,
                        K - dp[A - 1][B], dp);
            }
        }
 
        // Function to find the Kth lexicographically
        // smallest binary string with exactly
        // A zeroes and B ones
        function KthStringUtil(A, B, K) {
            // Stores the recurring states
            let dp = new Array(A + 1);
 
            for (let i = 0; i < dp.length; i++) {
                dp[i] = new Array(B + 1).fill(0);
            }
 
            // Calculate the dp values iteratively
            dp[0][0] = 1;
            for (let i = 0; i <= A; ++i) {
                for (let j = 0; j <= B; ++j) {
 
                    if (i > 0) {
 
                        // The last character was '0'
                        dp[i][j] += dp[i - 1][j];
                    }
                    if (j > 0) {
 
                        // The last character was '1'
                        dp[i][j] += dp[i][j - 1];
                    }
                }
            }
 
            // Print the binary string obtained
            document.write(KthString(A, B, K, dp));
 
            return 0;
        }
 
        // Driver Code
        let A = 3, B = 3, K = 7;
        KthStringUtil(A, B, K);
 
     // This code is contributed by Potta Lokesh
 
    </script>

Output: 

010110

 

Time Complexity: O(A*B)
Auxiliary Space: O(A*B)


 


Reffered: https://www.geeksforgeeks.org

Strings

Related
Check if a Regular Bracket Sequence can be formed with concatenation of given strings Check if a Regular Bracket Sequence can be formed with concatenation of given strings
Find any permutation of Binary String of given size not present in Array Find any permutation of Binary String of given size not present in Array
Minimize flips to make binary string as all 1s by flipping characters in substring of size K repeatedly Minimize flips to make binary string as all 1s by flipping characters in substring of size K repeatedly
Modify given string such that odd and even indices is lexicographically largest and smallest Modify given string such that odd and even indices is lexicographically largest and smallest
Length of Smallest Non Prime Subsequence in given numeric String Length of Smallest Non Prime Subsequence in given numeric String

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 12



 

Horje