Given three non-negative integers, X, Y, and K, the task is to find the Kth smallest lexicographical string having X occurrences of character ‘a’ and Y occurrences of character ‘b’.
Examples:
Input: X = 2, Y = 3, K = 3
Output: abbab
Explanation:
First lexicographical smallest string = “aabbb”.
Second lexicographical smallest string = “ababb”.
Third lexicographical smallest string = “abbab”.Input: X = 4, Y = 3, K = 4
Output: aaabbba
Naive Approach: The simplest approach is to generate all distinct permutations of the string X occurrences of character ‘a’ and Y occurrences of character ‘b’. Then first, sort the output string array in lexicographical order and print the Kth index string.
Time complexity: O(N*N!), where N is (X + Y)
Auxiliary Space: O(N!)
Efficient Approach: This problem has Overlapping Subproblems property and Optimal Substructure property. So this problem can be solved using Dynamic Programming. Like other typical Dynamic Programming(DP) problems, recomputation of the same subproblems can be avoided by constructing a temporary array that stores the results of subproblems. Follow the steps below to solve this problem.
- Initialize a 2D array, dp[][] where dp[i][j] denotes the number of strings containing i number of a’s, and j number of b’s.
- Iterate in the range [0, X] using the variable i:
- Iterate in the range [0, Y] using the variable j:
- If i is greater than 0, then update dp[i][j] to dp[i][j] + dp[i-1][j].
- If j is greater than 0, then update dp[i][j] to dp[i][j] + dp[i][j-1].
- Iterate in the range [0, Y] using the variable j:
- Now, recursively find the Kth lexicographical smallest string by calling the function kthString(int X, int Y, int K).
- Handle the base cases:
- If there are only ‘a’ characters present then return a string of all ‘a’ characters.
- If there are only ‘b’ characters present then return a string of all ‘b’ characters.
- If there are more than or equal to K strings that start with ‘a’, then return “a” + kthString(X-1, Y, K).
- Else the first character of the resultant string is ‘b’, return “b” + kthString(X, Y-1, K – dp[X-1][Y]).
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;const int MAX = 30;// Function to fill dp arrayvoid findNumString(int X, int Y, int dp[][MAX]){ // Initialize all the entries with 0 for (int i = 0; i < MAX; i++) { for (int j = 0; j < MAX; j++) { dp[i][j] = 0; } } // Update dp[0][0] to 1 dp[0][0] = 1; // Traverse the dp array for (int i = 0; i <= X; ++i) { for (int j = 0; j <= Y; ++j) { // Update the value of dp[i][j] if (i > 0) { dp[i][j] += dp[i - 1][j]; } if (j > 0) { dp[i][j] += dp[i][j - 1]; } } }}// Recursive function to find the Kth// lexicographical smallest stringstring kthString(int X, int Y, int K, int dp[][MAX]){ // Handle the base cases if (X == 0) { return string(Y, 'b'); } if (Y == 0) { return string(X, 'a'); } // If there are more than or equal // to K strings which start with a, // then the first character is 'a' if (K <= dp[X - 1][Y]) { return string("a") + kthString(X - 1, Y, K, dp); } // Otherwise the first character // of the resultant string is 'b' else { return string("b") + kthString(X, Y - 1, K - dp[X - 1][Y], dp); }}// Function to find the Kth// lexicographical smallest stringvoid kthStringUtil(int X, int Y, int K){ int dp[MAX][MAX]; // Function call to fill the dp array findNumString(X, Y, dp); // Print the resultant string cout << kthString(X, Y, K, dp) << '\n';}// Driver Codeint main(){ // Given Input int X = 4; int Y = 3; int K = 4; // Function Call kthStringUtil(X, Y, K); return 0;} |
Java
// Java program for the above approachpublic class GFG{static int MAX = 30;// Function to fill dp arraystatic void findNumString(int X, int Y, int dp[][]){ // Initialize all the entries with 0 for (int i = 0; i < MAX; i++) { for (int j = 0; j < MAX; j++) { dp[i][j] = 0; } } // Update dp[0][0] to 1 dp[0][0] = 1; // Traverse the dp array for (int i = 0; i <= X; ++i) { for (int j = 0; j <= Y; ++j) { // Update the value of dp[i][j] if (i > 0) { dp[i][j] += dp[i - 1][j]; } if (j > 0) { dp[i][j] += dp[i][j - 1]; } } }}// Recursive function to find the Kth// lexicographical smallest stringstatic String kthString(int X, int Y, int K, int dp[][]){ // Handle the base cases String x1 = ""; String y1 = ""; for (int i=0;i<Y;i++){ x1 += 'b'; } for (int i=0;i<X;i++){ y1 += 'a'; } if (X == 0) return x1; if (Y == 0) return y1; // If there are more than or equal // to K strings which start with a, // then the first character is 'a' if (K <= dp[X - 1][Y]) { return ("a" + kthString(X - 1, Y, K, dp)); } // Otherwise the first character // of the resultant string is 'b' else { return ("b" + kthString(X, Y - 1, K - dp[X - 1][Y], dp)); }}// Function to find the Kth// lexicographical smallest stringstatic void kthStringUtil(int X, int Y, int K){ int dp[][] = new int [MAX][MAX]; // Function call to fill the dp array findNumString(X, Y, dp); // Print the resultant string System.out.println(kthString(X, Y, K, dp));}// Driver Codepublic static void main(String args[]){ // Given Input int X = 4; int Y = 3; int K = 4; // Function Call kthStringUtil(X, Y, K); }}// This code is contributed by SoumikMondal |
Python3
# Python3 program for the above approachfrom typing import MappingMAX = 30# Function to fill dp arraydef findNumString(X, Y, dp): # Initialize all the entries with 0 for i in range(0, MAX): for j in range(0, MAX): dp[i][j] = 0 # Update dp[0][0] to 1 dp[0][0] = 1 # Traverse the dp array for i in range(0, X + 1): for j in range(0, Y + 1): # Update the value of dp[i][j] if (i > 0): dp[i][j] += dp[i - 1][j] if (j > 0): dp[i][j] += dp[i][j - 1]# Recursive function to find the Kth# lexicographical smallest stringdef kthString(X, Y, K, dp): # Handle the base cases x1 = "" y1 = "" for i in range(0, Y): x1 += 'b' for i in range(0, X): y1 += 'a' if (X == 0): return x1 if (Y == 0): return y1 # If there are more than or equal # to K strings which start with a, # then the first character is 'a' if (K <= dp[X - 1][Y]): return "a" + kthString(X - 1, Y, K, dp) # Otherwise the first character # of the resultant string is 'b' else: return "b" + kthString(X, Y - 1, K - dp[X - 1][Y], dp)# Function to find the Kth# lexicographical smallest stringdef kthStringUtil(X, Y, K): dp = [[0 for i in range(MAX)] for col in range(MAX)] # Function call to fill the dp array findNumString(X, Y, dp) # Print the resultant print(kthString(X, Y, K, dp))# Driver Code# Given InputX = 4Y = 3K = 4# Function CallkthStringUtil(X, Y, K)# This code is contributed by amreshkumar3 |
C#
// C# program for the above approachusing System;class GFG{ static int MAX = 30;// Function to fill dp arraystatic void findNumString(int X, int Y, int[,] dp){ // Initialize all the entries with 0 for (int i = 0; i < MAX; i++) { for (int j = 0; j < MAX; j++) { dp[i, j] = 0; } } // Update dp[0][0] to 1 dp[0, 0] = 1; // Traverse the dp array for (int i = 0; i <= X; ++i) { for (int j = 0; j <= Y; ++j) { // Update the value of dp[i][j] if (i > 0) { dp[i, j] += dp[i - 1, j]; } if (j > 0) { dp[i, j] += dp[i, j - 1]; } } }}// Recursive function to find the Kth// lexicographical smallest stringstatic string kthString(int X, int Y, int K, int[,] dp){ // Handle the base cases string x1 = ""; string y1 = ""; for (int i=0;i<Y;i++){ x1 += 'b'; } for (int i=0;i<X;i++){ y1 += 'a'; } if (X == 0) return x1; if (Y == 0) return y1; // If there are more than or equal // to K strings which start with a, // then the first character is 'a' if (K <= dp[X - 1, Y]) { return ("a" + kthString(X - 1, Y, K, dp)); } // Otherwise the first character // of the resultant string is 'b' else { return ("b" + kthString(X, Y - 1, K - dp[X - 1, Y], dp)); }}// Function to find the Kth// lexicographical smallest stringstatic void kthStringUtil(int X, int Y, int K){ int[,] dp = new int [MAX, MAX]; // Function call to fill the dp array findNumString(X, Y, dp); // Print the resultant string Console.WriteLine(kthString(X, Y, K, dp));}// Driver codestatic void Main(){ // Given Input int X = 4; int Y = 3; int K = 4; // Function Call kthStringUtil(X, Y, K);}}// This code is contributed by code_hunt. |
Javascript
<script>// JavaScript program for the above approachconst MAX = 30// Function to fill dp arrayfunction findNumString(X, Y, dp){ // Initialize all the entries with 0 for(let i = 0; i < MAX; i++) for(let j = 0; j < MAX; j++) dp[i][j] = 0 // Update dp[0][0] to 1 dp[0][0] = 1 // Traverse the dp array for(let i = 0; i < X + 1; i++) { for(let j = 0; j < Y + 1; j++) { // Update the value of dp[i][j] if (i > 0) dp[i][j] += dp[i - 1][j] if (j > 0) dp[i][j] += dp[i][j - 1] } }}// Recursive function to find the Kth// lexicographical smallest stringfunction kthString(X, Y, K, dp){ // Handle the base cases let x1 = "" let y1 = "" for(let i = 0; i < Y; i++) x1 += 'b' for(let i = 0; i < X; i++) y1 += 'a' if (X == 0) return x1 if (Y == 0) return y1 // If there are more than or equal // to K strings which start with a, // then the first character is 'a' if (K <= dp[X - 1][Y]) return "a" + kthString(X - 1, Y, K, dp) // Otherwise the first character // of the resultant string is 'b' else return "b" + kthString(X, Y - 1, K - dp[X - 1][Y], dp)}// Function to find the Kth// lexicographical smallest stringfunction kthStringUtil(X, Y, K){ let dp = new Array(MAX); for(let i = 0; i < MAX; i++) { dp[i] = new Array(MAX); } // Function call to fill the dp array findNumString(X, Y, dp) // Print the resultant document.write(kthString(X, Y, K, dp),"</br>")}// Driver Code// Given Inputlet X = 4let Y = 3let K = 4// Function CallkthStringUtil(X, Y, K)// This code is contributed by shinjanpatra</script> |
Output:
aaabbba
Time Complexity: O(X*Y)
Auxiliary Space: O(X*Y)
Efficient Approach: The above approach can further be optimized by iteratively implementing the KthString function. Follow the steps below to solve this problem:
- Declare a 2D array, dp where dp[i][j] denotes the number of strings containing i number of a’s, and j number of b’s.
- Iterate in the range [0, X] using the variable i:
- Iterate in the range [0, Y] using the variable j:
- If i is greater than 0, then update dp[i][j] to dp[i][j] + dp[i-1][j].
- If j is greater than 0, then update dp[i][j] to dp[i][j] + dp[i][j-1].
- Iterate in the range [0, Y] using the variable j:
- Now, iteratively find the Kth lexicographical smallest string.
- Traverse while X is greater than 0 and Y is greater than 0:
- If there are more than or equal to K strings that start with ‘a’, then print ‘a’ and decrement X by 1.
- Else, the first character of the resultant string is ‘b’, print ‘b’, and decrement Y by 1.
- If there are only ‘a’ characters present then print a string of all ‘a‘ characters.
- If there are only ‘b‘ characters present then print a string of all ‘b‘ characters.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;const int MAX = 30;// Function to fill dp arrayvoid findNumString(int X, int Y, int dp[][MAX]){ // Initialize all the entries with 0 for (int i = 0; i < MAX; i++) { for (int j = 0; j < MAX; j++) { dp[i][j] = 0; } } // Update dp[0][0] to 1 dp[0][0] = 1; // Traverse the dp array for (int i = 0; i <= X; ++i) { for (int j = 0; j <= Y; ++j) { // Update the value of dp[i][j] if (i > 0) { dp[i][j] += dp[i - 1][j]; } if (j > 0) { dp[i][j] += dp[i][j - 1]; } } }}// Iterative function to find the Kth// lexicographical smallest stringvoid kthString(int X, int Y, int K, int dp[][MAX]){ while (X > 0 and Y > 0) { // If there are more than or // equal to K strings which start // with a, then print 'a' if (K <= dp[X - 1][Y]) { cout << 'a'; X -= 1; } // Otherwise the first character // of the resultant string is b else { K -= dp[X - 1][Y]; cout << 'b'; Y -= 1; } } // If there are only 'a' characters // present then print a string of // all 'a' characters cout << string(X, 'a'); // If there are only 'b' characters // present then print a string of // all 'b' characters cout << string(Y, 'b'); cout << '\n';}// Function to find the Kth// lexicographical smallest stringvoid kthStringUtil(int X, int Y, int K){ int dp[MAX][MAX]; // Function call to fill the dp array findNumString(X, Y, dp); // Function call to find the // required string kthString(X, Y, K, dp);}// Driver Codeint main(){ // Given Input int X = 4; int Y = 3; int K = 4; // Function Call kthStringUtil(X, Y, K); return 0;} |
Java
// Java code for the above approachimport java.io.*;class Main { static final int MAX = 30; // Function to fill dp array static void findNumString(int X, int Y, int[][] dp) { // Initialize all the entries with 0 for (int i = 0; i < MAX; i++) { for (int j = 0; j < MAX; j++) { dp[i][j] = 0; } } // Update dp[0][0] to 1 dp[0][0] = 1; // Traverse the dp array for (int i = 0; i <= X; ++i) { for (int j = 0; j <= Y; ++j) { // Update the value of dp[i][j] if (i > 0) { dp[i][j] += dp[i - 1][j]; } if (j > 0) { dp[i][j] += dp[i][j - 1]; } } } } // Iterative function to find the Kth // lexicographical smallest string static void kthString(int X, int Y, int K, int[][] dp) { while (X > 0 && Y > 0) { // If there are more than or // equal to K strings which start // with a, then print 'a' if (K <= dp[X - 1][Y]) { System.out.print("a"); X -= 1; } // Otherwise the first character // of the resultant string is b else { K -= dp[X - 1][Y]; System.out.print("b"); Y -= 1; } } // If there are only 'a' characters // present then print a string of // all 'a' characters for (int i = 0; i < X; i++) { System.out.print("a"); } // If there are only 'b' characters // present then print a string of // all 'b' characters for (int i = 0; i < Y; i++) { System.out.print("b"); } System.out.println(); } // Function to find the Kth // lexicographical smallest string static void kthStringUtil(int X, int Y, int K) { int[][] dp = new int[MAX][MAX]; // Function call to fill the dp array findNumString(X, Y, dp); // Function call to find the // required string kthString(X, Y, K, dp); } // Driver Code public static void main(String[] args) { // Given Input int X = 4; int Y = 3; int K = 4; // Function Call kthStringUtil(X, Y, K); }}// This code is contributed by lokeshpotta20. |
Python3
# Python3 program for the above approachMAX = 30;# Function to fill dp arraydef find_num_string(X, Y, dp): # Initialize all the entries with 0 for i in range(MAX): for j in range(MAX): dp[i][j] = 0 # Update dp[0][0] to 1 dp[0][0] = 1 # Traverse the dp array for i in range(X+1): for j in range(Y+1): # Update the value of dp[i][j] if i > 0: dp[i][j] += dp[i-1][j] if j > 0: dp[i][j] += dp[i][j-1]# Iterative function to find the Kth# lexicographical smallest stringdef kth_string(X, Y, K, dp): while X > 0 and Y > 0: # If there are more than or # equal to K strings which start # with a, then print 'a' if K <= dp[X-1][Y]: print('a', end='') X -= 1 # Otherwise the first character # of the resultant string is b else: K -= dp[X-1][Y] print('b', end='') Y -= 1 # If there are only 'a' characters # present then print a string of # all 'a' characters print('a'*X, end='') # If there are only 'b' characters # present then print a string of # all 'b' characters print('b'*Y)# Function to find the Kth# lexicographical smallest stringdef kth_string_util(X, Y, K): dp = [[0 for j in range(MAX)] for i in range(MAX)] # Function call to fill the dp array find_num_string(X, Y, dp) # Function call to find the required string kth_string(X, Y, K, dp)# Driver Codeif __name__ == '__main__': # Given Input X = 4 Y = 3 K = 4 # Function Call kth_string_util(X, Y, K) # This code is contributed by ik_9 |
C#
// C# program to implement above approachusing System;using System.Collections.Generic;class GFG{ static int MAX = 30; // Function to fill dp array static void findNumString(int X, int Y, int[][] dp) { // Initialize all the entries with 0 for (int i = 0 ; i < MAX ; i++) { for (int j = 0 ; j < MAX ; j++) { dp[i][j] = 0; } } // Update dp[0][0] to 1 dp[0][0] = 1; // Traverse the dp array for (int i = 0 ; i <= X ; ++i) { for (int j = 0 ; j <= Y ; ++j) { // Update the value of dp[i][j] if (i > 0) { dp[i][j] += dp[i - 1][j]; } if (j > 0) { dp[i][j] += dp[i][j - 1]; } } } } // Iterative function to find the Kth // lexicographical smallest string static void kthString(int X, int Y, int K, int[][] dp) { while (X > 0 && Y > 0) { // If there are more than or // equal to K strings which start // with a, then print 'a' if (K <= dp[X - 1][Y]) { Console.Write('a'); X -= 1; } // Otherwise the first character // of the resultant string is b else { K -= dp[X - 1][Y]; Console.Write('b'); Y -= 1; } } // If there are only 'a' characters // present then print a string of // all 'a' characters String ans = ""; for(int i = 0 ; i < X ; i++){ ans+="a"; } Console.Write(ans); ans = ""; // If there are only 'b' characters // present then print a string of // all 'b' characters for(int i = 0 ; i < Y ; i++){ ans+="b"; } Console.Write(ans); Console.Write("\n"); } // Function to find the Kth // lexicographical smallest string static void kthStringUtil(int X, int Y, int K) { int[][] dp = new int[MAX][]; for(int i = 0 ; i < MAX ; i++){ dp[i] = new int[MAX]; } // Function call to fill the dp array findNumString(X, Y, dp); // Function call to find the // required string kthString(X, Y, K, dp); } // Driver Code public static void Main(string[] args){ // Given Input int X = 4; int Y = 3; int K = 4; // Function Call kthStringUtil(X, Y, K); }}// This code is contributed by subhamgoyal2014. |
Javascript
// Javascript program for the above approachconst MAX = 30;// Function to fill dp arrayfunction findNumString( X, Y, dp){ // Initialize all the entries with 0 for (let i = 0; i < MAX; i++) { for (let j = 0; j < MAX; j++) { dp[i][j] = 0; } } // Update dp[0][0] to 1 dp[0][0] = 1; // Traverse the dp array for (let i = 0; i <= X; ++i) { for (let j = 0; j <= Y; ++j) { // Update the value of dp[i][j] if (i > 0) { dp[i][j] += dp[i - 1][j]; } if (j > 0) { dp[i][j] += dp[i][j - 1]; } } }}// Iterative function to find the Kth// lexicographical smallest stringfunction kthString( X, Y, K, dp){ while (X > 0 && Y > 0) { // If there are more than or // equal to K strings which start // with a, then print 'a' if (K <= dp[X - 1][Y]) { document.write('a'); X -= 1; } // Otherwise the first character // of the resultant string is b else { K -= dp[X - 1][Y]; document.write('b'); Y -= 1; } } // If there are only 'a' characters // present then print a string of // all 'a' characters let ans = ""; for(let i = 0 ; i < X ; i++){ ans+="a"; } document.write(ans); ans = ""; // If there are only 'b' characters // present then print a string of // all 'b' characters for(let i = 0 ; i < Y ; i++){ ans+="b"; } document.write(ans);}// Function to find the Kth// lexicographical smallest stringfunction kthStringUtil( X, Y, K){ let dp=new Array(MAX); for(let i=0; i<MAX; i++) dp[i]=new Array(MAX); // Function call to fill the dp array findNumString(X, Y, dp); // Function call to find the // required string kthString(X, Y, K, dp);}// Driver Code// Given Inputlet X = 4;let Y = 3;let K = 4;// Function CallkthStringUtil(X, Y, K); |
Output:
aaabbba
Time Complexity: O(X*Y)
Auxiliary Space: O(X*Y)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
