Find Kth lexicographical ordered numeric string of length N with distinct products of each substring | Java program for the above approach ; Function to find the required String ; If the current length is equal to n exit from here only ; Iterate for all the characters ; Check if the product is present before ; If the current String is good then recurse for the next character ; Decrease all the products back to their original state ; Erase the last character ; Function to calculate kth ordered valid String ; Check for the base cases ; There are atmost 10 valid Strings for n = 1 ; Vector to keep a check on number of occurences of products ; Recursively construct the Strings ; Driver Code
import java . util . * ; class GFG { static String ans , s ; static int K ; static void getString ( int curlen , int N , int [ ] prod ) { if ( curlen == N ) { K -- ; if ( K == 0 ) ans = s ; return ; } char ch ; int ok , t , i ; for ( ch = '2' ; ch <= '9' ; ch ++ ) { s += ch ; ok = 1 ; t = 1 ; for ( i = curlen ; i >= 0 && s . length ( ) > i ; i -- ) { t *= s . charAt ( i ) - 48 ; if ( prod [ t ] != 0 ) ok = 0 ; prod [ t ] ++ ; } if ( ok != 0 ) getString ( curlen + 1 , N , prod ) ; t = 1 ; for ( i = curlen ; i >= 0 && s . length ( ) > i ; i -- ) { t *= s . charAt ( i ) - 48 ; prod [ t ] -- ; } if ( s . length ( ) > 0 ) s = s . substring ( 0 , s . length ( ) - 1 ) ; } } static String kthValidString ( int N ) { if ( N > 10 ) { return " - 1" ; } if ( N == 1 ) { if ( K > 10 ) { return " - 1" ; } String s = " " ; K -- ; s += ( K + '0' ) ; return s ; } ans = " - 1" ; s = " " ; int [ ] prod = new int [ 10005 ] ; getString ( 0 , N , prod ) ; return ans ; } public static void main ( String [ ] args ) { int N = 3 ; K = 4 ; System . out . print ( kthValidString ( N ) ) ; } }