Lexicographically Kth | Java program for the above approach ; Function to fill dp array ; Initialize all the entries with 0 ; Update dp [ 0 ] [ 0 ] to 1 ; Traverse the dp array ; Update the value of dp [ i ] [ j ] ; Recursive function to find the Kth lexicographical smallest string ; Handle the base cases ; If there are more than or equal to K strings which start with a , then the first character is ' a ' ; Otherwise the first character of the resultant string is ' b ' ; Function to find the Kth lexicographical smallest string ; Function call to fill the dp array ; Print the resultant string ; Driver Code ; Given Input ; Function Call
public class GFG { static int MAX = 30 ; static void findNumString ( int X , int Y , int dp [ ] [ ] ) { for ( int i = 0 ; i < MAX ; i ++ ) { for ( int j = 0 ; j < MAX ; j ++ ) { dp [ i ] [ j ] = 0 ; } } dp [ 0 ] [ 0 ] = 1 ; for ( int i = 0 ; i <= X ; ++ i ) { for ( int j = 0 ; j <= Y ; ++ j ) { if ( i > 0 ) { dp [ i ] [ j ] += dp [ i - 1 ] [ j ] ; } if ( j > 0 ) { dp [ i ] [ j ] += dp [ i ] [ j - 1 ] ; } } } } static String kthString ( int X , int Y , int K , int dp [ ] [ ] ) { 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 ( K <= dp [ X - 1 ] [ Y ] ) { return ( " a " + kthString ( X - 1 , Y , K , dp ) ) ; } else { return ( " b " + kthString ( X , Y - 1 , K - dp [ X - 1 ] [ Y ] , dp ) ) ; } } static void kthStringUtil ( int X , int Y , int K ) { int dp [ ] [ ] = new int [ MAX ] [ MAX ] ; findNumString ( X , Y , dp ) ; System . out . println ( kthString ( X , Y , K , dp ) ) ; } public static void main ( String args [ ] ) { int X = 4 ; int Y = 3 ; int K = 4 ; kthStringUtil ( X , Y , K ) ; } }